洛谷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;
}