POJ 2184 Cow Exhibition 01双肩包

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 1000000007
using 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;
}

POJ 2184 Cow Exhibition 01双肩包

相关推荐