POJ 2184 Cow Exhibition 01背包
题意就是给出n对数
每对xi, yi 的值范围是-1000到1000
然后让你从中取若干对
使得sum(x[k]+y[k]) 最大并且非负 且 sum(x[k]) >= 0 sum(y[k]) >= 0 其中 k为所有你取到的标号
然后刚开始没什么思路
后来想想。 这就是背包吧。
将x看成花费，y看成价值
然后dp[i]表示在花费了i情况时价值最大是多少
注意到数值有负数
所以要加一些技巧
所有x的总值可能是-10w，而所有y的总值也可能是-10W
那么可以dp[100000] = 100000
以这个作为什么都没取的状态。
然后我们要判断第一个数的和是否非负就是判断 dp[i]中的i是否小于10W
然后判断第二个数的和非负就是判断dp[i]是否小于10W
这样的好处是我们只需要在转移方程时，
如果花费为c，价值为w
判断dp[i - c] 是否为0即可判断其状态是否合法
这是因为我们要的是恰好总和为i的状态。
所以起始的合法状态只有1个
然后在转移的时候也需要注意
开一个数组就行了。
传统的01背包转移， 使用滚动数组的方法是倒着来
那么对于这题有正花费有负花费。
所以对于负花费很显然是正着来的。
而且这题直接枚举1到20W这样花费 就比较慢。
因为有很多状态的花费还没有用到。
所以每次计算一下可能用到的间隔。
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <map>#include <vector>#define MAXN 200005#define INF 1000000007using namespace std;int dp[MAXN];int mid = 100002;int n;int main(){ dp[mid] = mid; int c, w; scanf("%d", &n); int l = mid, r = mid; for(int i = 1; i <= n; i++) { scanf("%d%d", &c, &w); l = min(l, l + c); r = max(r, r + c); if(c > 0) { for(int j = r; j >= l; j--) if(dp[j - c]) dp[j] = max(dp[j - c] + w, dp[j]); } else { for(int j = l; j <= r; j++) if(dp[j - c]) dp[j] = max(dp[j - c] + w, dp[j]); } } int res = 0; for(int i = mid; i < MAXN; i++) if(dp[i] >= mid) res = max(res, i - mid + dp[i] - mid); printf("%d\n", res); return 0;}