Codeforces Round #214 (Div. 2) C. Dima and Salad 背包DP

链接：

http://codeforces.com/contest/366/problem/C

题意：

给出n个物品，有两个属性，问最后第一个属性的总和是第二个属性的k倍的时候，第一个属性最大是多少。

题解：

我们将物品做一个变形，重量为a[i]-b[i]*k,收益是a，那么我们只需要对重量为正的做一遍背包，对质量为负的取绝对值做一遍背包，然后重量相等的背包的收益之和就是当前重量下的最大收益.

注意，一定要把dp数组初始化为-0x3f，不然结果就是错误的，因为这道题背包比较特殊，必须是装满的

代码：

31 int n, k;
32 int a[MAXN], b[MAXN];
33 const int MAXN2 = MAXN*MAXN;
34 int dp0[MAXN2], dp1[MAXN2];
35 
36 int main() {
37     ios::sync_with_stdio(false), cin.tie(0);
38     cin >> n >> k;
39     rep(i, 0, n) cin >> a[i];
40     rep(i, 0, n) {
41         cin >> b[i];
42         b[i] = a[i] - k*b[i];
43     }
44     memset(dp0, -0x3f, sizeof(dp0));
45     memset(dp1, -0x3f, sizeof(dp1));
46     dp0[0] = dp1[0] = 0;
47     rep(i, 0, n)
48         if (b[i] >= 0)
49             per(j, b[i], MAXN2)
50             dp1[j] = max(dp1[j], dp1[j - b[i]] + a[i]);
51     rep(i, 0, n)
52         if (b[i] < 0)
53             per(j, -b[i], MAXN2)
54             dp0[j] = max(dp0[j], dp0[j + b[i]] + a[i]);
55     int ans = dp1[0] > 0 ? dp1[0] : -1;
56     rep(i, 1, MAXN2) ans = max(ans, dp0[i] + dp1[i]);
57     cout << ans << endl;
58     return 0;
59 }