题意概述
给定四个数组$M, P, L, R$，要求构造一个数组$T$，使得
$$
\sum_{i=1}^N M_iT_i=0 \ (L_i \le T_i \le R_i)
$$
求$\sum_{i=1}^N P_iT_i$的最大值。
数据范围：$1 \le N \le 200, \ 1 \le M_i \le 20, \ 0 \le P_i \le 10^5, \ -25 \le L_i \lt R_i \le 25$。
算法分析
令$D_i=T_i-L_i$，那么限制条件变为$\sum_{i=1}^N M_iD_i=-\sum_{i=1}^N M_iL_i \ (0 \le D_i \le R_i-L_i)$，要求的值变为$\sum_{i=1}^N P_iD_i+\sum_{i=1}^N P_iL_i$。这就相当于有$N$种物品，第$i$种物品有$(R_i-L_i)$个，每一个的体积为$M_i$，价值为$P_i$，背包的体积为$-\sum_{i=1}^N M_iL_i$，求物品恰好装满背包时的最大价值。这是分组背包问题，用单调队列优化 DP 即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <cstdio>
#include <cstring>
int min(int a, int b) {
return a < b ? a : b;
}
static const int N = 205;
int p[N], m[N], u[N], l[N];
int f[N << 10], q1[N << 10], q2[N << 10];
int main() {
int n;
while (~ scanf("%d", &n)) {
int v = 0, w = 0;
for (int i = 0; i < n; ++ i) {
scanf("%d%d%d%d", &p[i], &m[i], &l[i], &u[i]);
if (l[i]) u[i] -= l[i], v -= l[i] * m[i], w -= l[i] * p[i];
}
memset(f, -0x3f, sizeof f), f[0] = 0;
for (int i = 0; i < n; ++ i) {
u[i] = min(u[i], v / m[i]);
for (int d = 0; d < m[i]; ++ d) {
int l = 1, r = 0;
for (int j = 0; j <= (v - d) / m[i]; ++ j) {
int val = f[j * m[i] + d] - j * p[i];
while (l <= r && q1[r] < val) -- r;
q2[++ r] = j, q1[r] = val;
if (j - q2[l] > u[i]) ++ l;
f[j * m[i] + d] = q1[l] + j * p[i];
}
}
}
printf("%d\n", f[v] - w);
}
return 0;
}
|