题解 P2340 【奶牛会展】

· · 题解

我们发现这道题对于每头奶牛无非也是选或不选两种状态。那么01背包同样是选或不选两种状态，不妨试着将本题转成01背包？那么何为代价？发现有两个元素：情商，智商。而这两个元素对于题来说都是等价的，那么是不是任选一个作为背包代价也可以呢？我们来试试：假设智商为代价，即 f[j] 为当智商为 j 时情商的最大值。（为什么 f[j] 不能表示为智商与情商的和 后面再说）再思考状态转移，模仿01背包，得出方程 

    f[j]=max(f[j],f[j-cow[i].s]+cow[i].f);

（cow.s 为智商，cow.f 为情商）但是又由题可得转移时 j 有可能在某个时刻为负数，当然最终答案里的 j 和 f[j] 都大于等于 0，为了防止数组越界，我们可以把 j 整体向右移动一些单位，移动多少呢？因为1 ≤ N ≤ 400 且 −1000 ≤ 奶牛的情商和智商 ≤ 1000，所以任意一个时刻 j 最小为 400 ×（-1000）= -400000，最大为 400 ×（1000）= 400000 那么我们将 j 整体向右移 400000 就好了。移动完后的 f[j] 就是移动前的 f[j-400000] 。例如移动后的 400000 就对应着移动前的 0 也就是原来的最小值。而移动后的 800000 就对应着移动前的 400000 也就是原来的最大值。至此我们便已经解决了 j 为负时的问题。现在已经很像01背包了（智商为代价，情商为价值，背包容量为 0～800000），但是还有一点不同，就是物品代价有可能为负，这就导致了我们不能跟01背包一样全部都倒序枚举背包容量然后进行状态转移，若当我们从800000开始倒序枚举，假设我们已经枚举过 j = 666666 这个状态并且当前我们在 j = 666660，同时当前的 cow.s = -6，那么此时我们就会回退到 666666 这个状态，万一在状态 666666 已经把 cow 选了一遍，现在就会又再选一遍，显然这样是不行的。既然有些为负，那么我们就只把 cow.s 为负的几个奶牛单独用正序枚举，这样若要减去一个 cow.s 也不会出现重选的情况了。至此，一个完整DP就设计出来了：

    for(int i=1;i<=n;i++) {
        if(cow[i].s>=0) {
            for(int j=800000;j>=cow[i].s;j--)       //非负数就倒叙枚举
                f[j]=max(f[j],f[j-cow[i].s]+cow[i].f);
        }else {
            for(int j=0;j<=800000+cow[i].s;j++)     //负数就正序枚举
                f[j]=max(f[j],f[j-cow[i].s]+cow[i].f);
        }
    }

在最终找答案的时候从 j = 400000 -> 800000 范围内找就行了，因为 400000 对应着移动前的 j = 0（智商和要为非负数）。 为什么 f[j] 不能表示为智商与情商的和？
因为在找答案时就无法判断当前状态的情商和是否为负数。

代码：
跑得比较慢～

#include <cstdio>
#include <cstring>
using namespace std;
int n,m,maxx=-2147483647,f[800005];
struct {
    int s,f;
}cow[405];
int max(int a,int b) {
    return a>b?a:b;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&cow[i].s,&cow[i].f);
    memset(f,-0x3f,sizeof(f));
    f[400000]=0;
    for(int i=1;i<=n;i++) {
        if(cow[i].s>=0) {
            for(int j=800000;j>=cow[i].s;j--)
                f[j]=max(f[j],f[j-cow[i].s]+cow[i].f);
        }else {
            for(int j=0;j<=800000+cow[i].s;j++)
                f[j]=max(f[j],f[j-cow[i].s]+cow[i].f);
        }
    }
    for(int i=400000;i<=800000;i++)
        if(f[i]>=0)
            maxx=max(maxx,f[i]+i-400000);
    printf("%d\n",maxx);
    return 0;
}