P2340 [USACO03FALL] Cow Exhibition G
用 \(f[i][j][k]\) 表示前 \(i\) 个元素，智商之和为 \(j\)，情商之和为 \(k\)。这样表示显然很冗余，因为答案已经包含在状态里面了。
一个常见的技巧是将键挪到值处，即用 \(f[i][j]\) 来表示前 \(i\) 个元素智商之和为 \(j\)，情商之和的最大值。
转移和背包类似：
\[f[i][j]\gets \min(f[i-1][j],f[i-1][j-x[i]]+y[i])
\]
需要注意两点：
- 由于第二维可能出现负数，所以存储时需要整体平移一个值域。
- 必须滚动数组，否则会 MLE。滚动数组时 \(j\) 的枚举方向需要根据 \(x[i]\) 决定。\(x[i]\) 为正则倒序枚举，\(x[i]\) 为负则正序枚举。
总时间 \(O(nV)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=405,V=400000;
struct Nd{int x,y;}a[N];
int n,f[2*V+5],ans;
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;memset(f,-0x3f,sizeof f);f[V]=0;for(int i=1;i<=n;i++){//a[i].x>0则倒序 否则正序 if(a[i].x>0){for(int j=V+V;j>=a[i].x;j--){f[j]=max(f[j],f[j-a[i].x]+a[i].y);}}else{for(int j=0;j<=V+V+a[i].x;j++){f[j]=max(f[j],f[j-a[i].x]+a[i].y);}}}for(int i=0;i<=V;i++){if(f[i+V]>=0) ans=max(ans,i+f[i+V]);}cout<<ans<<"\n";return 0;
}