洛谷P3188 [HNOI2007]梦幻岛宝珠题解

题目链接：P3188 [HNOI2007]梦幻岛宝珠

题意：

给你 $n$ 颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过 $W$，且总价值最大，并输出最大的总价值。

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 100$，$1\le W,w_i,v_i \le 2^{30}$。
保证每个 $w_i$ 能写成 $a \times 2^b\space (a,b \in \mathbb N)$ 的形式，$a \leq 10$ , $b \leq 30$，且答案不超过 $2^{30}$。

注：下文中将使用 $m$ 代替 $W$。

这么大的背包容量，肯定不是朴素的背包问题

可以发现数据范围里强调了 “保证每个 $w_i$ 能写成 $a \times 2^b\space (a,b \in \mathbb N)$ 的形式”

尽管有

$\forall\, x \in \mathbb{N},\exist\, a,b \in \mathbb{N},\ \bold{s.t. }\ \ x=a\times 2^b$

但是这里的 $a\le 10$ 却十分特殊，这意味着我们可以从这个角度思考解法

考虑利用泛化物品的思想

首先将每件物品按 $b$ 进行分组，在每一组内dp

设 $f[i][j]$ 为在所有满足 $b=i$ 的物品中选择若干（不妨设为 $k$ ）件物品，且总体积 $j^{\prime}$ 满足

$\sum{a_k}\times 2^i \le j \times 2^i \Rightarrow \sum a_k \le j \Rightarrow j^{\prime} \le j$

时的最大价值。

然后考虑合并泛化物品，即 $b$ 不同的物品之间的转移

令 $g[i][j]$ 表示仅使用 $b \in [0,i]$ 的物品，且 $b=i$ 的物品所占空间为 $j$ ，$b\in [0,i-1]$ 的物品所占空间为 $m\&(2^i-1)$ 时的最大价值

这里的 $\&$ 表示二进制按位与，不难发现 $m\&(2^i-1)$ 就是 $m$ 的第 $1$ 到 $i-1$ 位

转移方程如下

$g[i][j]=\max_{0\le k \le j}(g[i][j],f[i][j-k]+g[i-1][\min(10n,2k + [m \text{ 第 }i\text{ 位为 }1]])$

注：这里的第 $i$ 位是从第 $1$ 位开始数的

写成代码就是

g[i][j]=max(g[i][j],f[i][j-k]+g[i-1][min(10*n,k*2+((m>>(i-1))&1))]);

即从 $j\times 2^i$ 中抽出来 $k\times 2^i$ 的体积给 $b \in[0,i-1]$ 的物品

这里加上 $\min(10n,\dots)$ 的原因是 $(\dots)$ 处可能超出了 $\sum\limits_{0\le k \le i-1} j_k$ 的一个较宽松的上限 $10n$

但是这个上界并不容易达到，因此为了避免讨论，使用 $\min$ 即可

因此答案为 $g[m\text{ 的位数}][1]$

时间复杂度 $O(Qn^2\log m)$ ，但是常数巨大无比（别急，后面还有…

代码1：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(115)
int n,m,num[32];
int a[32][N],v[32][N],f[32][N*10],g[32][N*10];
#define mem(x) memset(x,0,sizeof(x));
void clear(){mem(a);mem(num);mem(v);mem(f);mem(g);}
signed main()
{
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(read(n),read(m),n+m!=-2)
    {
        clear();
        for(int i=1,x,y; i<=n; i++)
        {
            read(x);read(y);
            int cnt=0;
            while(!(x&1)){x>>=1,++cnt;}
            ++num[cnt];
            a[cnt][num[cnt]]=x;
            v[cnt][num[cnt]]=y;
        }
        int cnt=32;
        while(m<=(1ll<<(--cnt)));
        for(int k=0; k<=cnt; k++)
            for(int i=1; i<=num[k]; i++)
                for(int j=10*num[k]; j>=a[k][i]; j--)
                    f[k][j]=max(f[k][j],f[k][j-a[k][i]]+v[k][i]);
        for(int i=0; i<=10*num[0]; i++)
            g[0][i]=f[0][i];
        for(int i=1; i<=cnt; i++)
            for(int j=0; j<=10*n; j++)
                for(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))]);           
        write(g[cnt][1]);pc('\n');
    }
    return 0;
}

注意到上面的代码，虽然可以过

但是一共跑了1.20s，~~这是不可接受的~~（逃

考虑优化一下

注意到这个上界 $10n$ 一般不容易达到（前面提到过

因此我们会做很多无效枚举

可以开一个数组 $s[i]$ 表示所有 $b=i$ 的物品的 $a$ 之和

同时，注意到 $f$ 其实可以重复利用，考虑改变一下枚举顺序

这样就可以在 39ms 左右跑出来啦！

代码2：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(115)
int n,m,num[32],s[32];
int a[32][N],v[32][N],f[32][N*10];
#define mem(x) memset(x,0,sizeof(x));
void clear(){mem(a);mem(num);mem(v);mem(f);mem(s);}
signed main()
{
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(read(n),read(m),n+m!=-2)
    {
        clear();
        for(int i=1,x,y; i<=n; i++)
        {
            read(x);read(y);
            int cnt=0;
            while(!(x&1)){x>>=1,++cnt;}
            ++num[cnt];s[cnt]+=x;
            a[cnt][num[cnt]]=x;
            v[cnt][num[cnt]]=y;
        }
        int cnt=32;
        while(m<=(1ll<<(--cnt)));
        for(int k=0; k<=cnt; k++)
            for(int i=1; i<=num[k]; i++)
                for(int j=s[k]; j>=a[k][i]; j--)
                    f[k][j]=max(f[k][j],f[k][j-a[k][i]]+v[k][i]);
        for(int i=1; i<=cnt; i++)
        {
            s[i]+=(s[i-1]+1)>>1; // 向上取整
            for(int j=s[i]; j>=0; j--) // 倒序枚举，防止答案被错误覆盖
                for(int k=0; k<=j; k++)
                    f[i][j]=max(f[i][j],f[i][j-k]+f[i-1][min(s[i-1],(k<<1)|((m>>(i-1))&1))]);
        }
        write(f[cnt][1]);pc('\n');
    }
    return 0;
}