题目链接；
1.题外话
咕咕咕
2.解题意
咕咕咕，比较容易理解，智商情商需要捆绑在一起。
3.找思路
每一个奶牛都只包含两种情况：选， 不选。并且很明显这不是一个完全背包。
考虑套一套01背包的板子：每个奶牛都有两个参数：智商，情商。在01背包板子中，每一个物品都有两个参数：体积，价值。
于是，第一种做法也就浮现而出：把智商设为体积，把情商当做价值，跑01背包。跑完后枚举一下智商大小，加上当前智商状态值所对应的的最大情商，取max即可。
按理说是可以过的。但是偏偏有几个奶牛不是智商捉急负数，就是情商要命负数，再不就是歪比哇卜双负数。
对于智商为负数的情况，众所周知数组下标不能有负数，于是我们可以将数组往右平移一整个范围。这样保证即使智商全取负数中的最小值，也依然>=0。具体表现在代码中，就是数组多开一倍，枚举智商值的j增大一倍即可。
j对于情商为负数的情况。由于一维的01背包是从大到小枚举以保证每个物品只选一次。如果是负数，那么减去负数得正数，你将获得从小往大里枚举的效果（完全背包）。每个牛牛是独一无二的所以我们不能多次枚举，很明显不符合题意。
解决方法是遇到负数，你人为的把枚举的顺序倒过来即可。目的是保证每一个牛仅被选一次。，注意一下枚举智商的j的范围。
代码：
#include<cstdio> #include<cstring> #include<iostream> #define N 407 using namespace std; inline int read() { int ans=0; char ch=getchar(),last=' '; while(ch>'9'||ch<'0')last=ch,ch=getchar(); while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); return last=='-'?-ans:ans; } struct cow{ int iq,eq; }cow[N]; int n,f[800007],maxn; int main(){ scanf("%d",&n); memset(f,-0x3f,sizeof(f)); f[400000]=0; for(int i=1;i<=n;i++) { scanf("%d%d",&cow[i].iq,&cow[i].eq); } for(int i=1;i<=n;i++) { if(cow[i].iq>=0) { for(int j=800000;j>=cow[i].iq;j--) f[j]=max(f[j],f[j-cow[i].iq]+cow[i].eq); } else { for(int j=0;j<=800000+cow[i].iq;j++) f[j]=max(f[j],f[j-cow[i].iq]+cow[i].eq); } } for(int i=400000;i<=800000;i++) { if(f[i]>=0) maxn=max(maxn,f[i]+i-400000); } printf("%d",maxn); }
完结撒花。
祝各位NOIP2020 RP++