CodeForces366C. Dima and Salad(01背包变形好题)

题目大意：

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

题目分析：

我们将物品做一个变形，重量为a[i]-b[i]*k,收益是a，那么我们只需要对重量为正的做一遍背包，对质量为负的取绝对值做一遍背包，然后重量相等的背包的收益之和就是当前重量下的最大收益.注意转移中，要排除从不存在的状态中转移过来的情况！ #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int maxn = 105; int dp1[maxn*maxn], dp2[maxn*maxn]; int a[maxn], b[maxn], c[maxn]; int main() { int n, k; while(cin >> n >> k) { for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) { cin >> b[i]; c[i] = a[i] - b[i] * k; } memset(dp1, -1, sizeof(dp1)); memset(dp2, -1, sizeof(dp2)); dp1[0] = dp2[0] = 0; for(int i = 1; i <= n; i++) { if(c[i] >= 0) for(int j = 10005; j >= c[i]; j--) { if(dp1[j-c[i]] != -1) dp1[j] = max(dp1[j], dp1[j-c[i]] + a[i]); } else { c[i] = -c[i]; for(int j = 10005; j >= c[i]; j--) { if(dp2[j-c[i]] != -1) dp2[j] = max(dp2[j], dp2[j-c[i]] + a[i]); } } } int ans = 0; for(int i = 0; i < 10005; i++) if(dp1[i] != -1 && dp2[i] != -1) { ans = max(ans, dp1[i] + dp2[i]); } if(ans == 0) cout << -1 << endl; else cout << ans << endl; } return 0; }