P3188 [HNOI2007] 梦幻岛宝珠

当01背包的体积范围达到2^30时，应该怎么办？ 题目中已经注明每一个物品的体积都满足$ 2^a*b $ 所以根据$ 2^a $，可以把所有物品分组 令$ f[ i ][ j ] $表示体积为$ 2^i*j $ 时的最大价值 对每一组分别进行01背包即可求出 再改变一下f数组的含义，用已经得到的答案进行组间dp $ f[ i ][ j ] $表示体积为$ 2^i*j+(m$&$(1<<i)-1) $时的最大价值 状态转移方程为 $ chmax(f[i][j],f[i][k]+f[i-1][(j-k<<1)+(m>>i-1)$&$ 1]) $ ```cpp #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; int n,m,ans,f[31][1005];//j*2^i inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } int main() { while (1) { n=read(),m=read(); if (n<0) break; memset(f,0,sizeof(f)); ans=0; for (reg int i=1;i<=n;i++) { int w=read(),v=read(),k=0; while (!(w&1)) ++k,w>>=1; for (reg int j=min(m>>k,1000);j>=w;j--) { f[k][j]=max(f[k][j],f[k][j-w]+v); ans=max(ans,f[k][j]); } } for (reg int i=1;i<31&&(1<<i)<m;i++) for (reg int j=min(m>>i,1000);~j;j--) { for (reg int k=j;~k;k--) f[i][j]=max(f[i][j],f[i][k]+f[i-1][min((j-k<<1)+((m>>i-1)&1),1000)]); ans=max(ans,f[i][j]); } printf("%d\n",ans); } return 0; } ```