题目描述：P2340 [USACO03FALL] Cow Exhibition G

题目描述

奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对 $N$ 头奶牛进行了面试，确定了每头奶牛的智商和情商。

贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。

输入格式

第一行：单个整数 $N$，$1\le N\le 400$。

第二行到第 $N+1$ 行：第 $i+1$ 行有两个整数：$S_i$ 和 $F_i$，表示第 $i$ 头奶牛的智商和情商，$-1000\le S_i,F_i\le 1000$。

输出格式

输出单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出 $0$。

输入输出样例 #1

输入 #1

5
-5 7
8 -6
6 -3
2 1
-8 -5

输出 #1

8

说明/提示

选择第一头，第三头，第四头奶牛，智商和为 $-5+6+2=3$，情商和为 $7-3+1=5$。

再加入第二号奶牛可使总和提升到 $10$，不过由于情商和变成负的了，所以是不允许的。

思路

智商为体积，情商为价值，01背包求最大价值。最后扫一遍数组，求体积+价值的最大值
难点：体积可负
出现问题1：下标为负数
解决方法：数组整体向右偏移，最小智商和为-4e5，因此，向右偏移4e5
出现问题2：下标会增大，和01背包状态转移方程变化相反
解决方法：将枚举体积维度逆序

代码

#include<bits/stdc++.h>
using namespace std;
const int N=400+10,M=8e5+10;//M向右偏移4e5
int n,V=8e5,v,w,f[M],ans;//v智商,w情商
int main(){
    cin>>n;
    memset(f,-0x3f,sizeof f);
    f[400000]=0;//因为向右偏移了4e5
    for(int i=1;i<=n;i++){
        cin>>v>>w;
        if(v>=0) for(int j=V;j>=v;j--) f[j]=max(f[j],f[j-v]+w);
        else for(int j=0;j<=V+v;j++) f[j]=max(f[j],f[j-v]+w);
    }
    for(int j=400000;j<=800000;j++)
        if(f[j]>=0) ans=max(ans,j+f[j]-400000);
    cout<<ans;
    return 0;
}

结果