题解 P3188 【[HNOI2007]梦幻岛宝珠】

HC20050615 · 2020-12-02 15:04:19 · 题解

题意分析

普通01背包，花费、价值都贼大。不过花费一定能表示成 a\times2^b(a\leq10,b\leq30)。

思路

直接用01背包空间时间绝对都炸。（一道紫题怎么可能那么简单）

不过像这种数据大到起飞的背包题，多半都会有一些特殊条件（不然怎么做）

所以我们一定要从这道题的特殊条件上考虑。

虽然花费很大，但是花费表示成的 a,b 以及 n 都很小。所以我们可以考虑对 b 不同的物品分开背包，再进行合并。

对于每一个背包，其价值不变，花费为物品价值对应的 a，然后就可以直接背包了。

所以困难的在于合并。我们先令上方所求的背包为 f[i][j]。表示对于 b 为 i 的物品进行背包，当容量为 j 的时候的最大价值。

然后我们再设一个数组 g[i][j] 表示当使用 b 为 0\sim i 的物品进行背包，b 为 i 的物品所占空间为 j 时，剩余物品（即 b 为 1\sim i-1）所占空间为 m\&((1<<i)-1) 的最大价值。

而这个 m\&((1<<i)-1) 简单来说就是 m 的 i 位以下的值。

接着我们就可以考虑转移了，转移方程式如下：

那这个方程是什么意思呢？？

我们可以这样想，我们从 j 中拆除 k，拿给剩下的物品放。而高位向低位转移时会 \times 2，然后再加上 m 中该位上的值（m>>(i-1))\&1 表示 m 在 i-1 位上的值）

最后我们只需要输出 g[m 的位数][1]就可以了（因为 m 的首位一定是 1）

Code

#include<bits/stdc++.h>
using namespace std;
inline int read() 
{
    char c=getchar();
    int x=0,bj=1;
    while(c<'0'||c>'9') 
    {
        if(c=='-') 
        {
            bj=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9') 
    {
        x=x*10+(c^48);
        c=getchar();
    }
    return x*bj;
}
int n,m;
int num[31];
int a[31][101];
int w[31][101];
int f[31][1001];
int g[31][1001];
int main()
{
    n=read(),m=read();
    while(n+m!=-2)
    {
        memset(a,0,sizeof(a));
        memset(num,0,sizeof(num));
        memset(w,0,sizeof(w));
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(register int i=1;i<=n;i++)
        {
            register int x=read();
            int cnt=31;
            while(x%(1<<(--cnt)));
            a[cnt][++num[cnt]]=x/(1<<cnt);
            w[cnt][num[cnt]]=read();
        }
        register int cnt=31;
        while(m<=(1<<(--cnt)));
        for(register int t=0;t<=cnt;t++)
        {
            for(register int i=1;i<=num[t];i++)
            {
                for(register int j=10*num[t];j>=a[t][i];j--)
                {
                    f[t][j]=max(f[t][j],f[t][j-a[t][i]]+w[t][i]);
                }
            }
        }
        for(register int j=0;j<=10*num[0];j++)
        {
            g[0][j]=f[0][j];
        }//对0进行初始化
        for(register int i=1;i<=cnt;i++)
        {
            for(register int j=0;j<=10*n;j++)//因为每位上最多就是10*n，可以节省时间
            {
                for(register int k=0;k<=j;k++)
                {
                    g[i][j]=max(g[i][j],f[i][j-k]+g[i-1][min(10*n,k*2+((m>>(i-1))&1))]);
                }
            }
        }
        printf("%d\n",g[cnt][1]);
        n=read(),m=read();
    }
    return 0;
}