POJ 2184 Cow Exhibition 01背包-白红宇

POJ 2184 Cow Exhibition 01背包

阅读量：7018 次

发布时间：2019-06-28

本文共 1260 字，大约阅读时间需要 4 分钟。

题意就是给出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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #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;}