洛谷 2340 奶牛会展
【题解】
我们把智商ai当成重量，把情商bi当成价值，可以把这道题转化为一道经典的01背包问题。
f[i]=max(f[i],f[i-a[i]]+b[i]).
但是转化后与原来的01背包有一些不同：
转移必须支持负数，所以我们把f的下标平移400000个单位，全部变成正数。
有些代价为负数，这时我们不能倒着枚举，必须改变枚举顺序，避免重复选择同一个数。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N (2000) 7 #define M (800000) 8 using namespace std; 9 int n,ans,f[M+10],a[N],b[N]; 10 inline int read(){ 11 int k=0,f=1; char c=getchar(); 12 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 13 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 14 return k*f; 15 } 16 int main(){ 17 n=read(); 18 for(rg int i=1;i<=n;i++) a[i]=read(),b[i]=read(); 19 memset(f,-0X7f7f7f7f,sizeof(f)); f[M/2]=0; 20 for(rg int i=1;i<=n;i++){ 21 if(a[i]>=0) 22 for(rg int j=M;j>=a[i];j--) f[j]=max(f[j],f[j-a[i]]+b[i]); 23 else for(rg int j=0;j<=M+a[i];j++) f[j]=max(f[j],f[j-a[i]]+b[i]); 24 } 25 for(rg int i=M/2;i<=M;i++){ 26 if(f[i]>0) ans=max(ans,f[i]+i-M/2); 27 // printf("%d ",i-M/2); 28 } 29 printf("%d ",ans); 30 return 0; 31 }