P3188 [HNOI2007] 梦幻岛宝珠

2018-07-11 14:58:39


当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]) $

#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;
}