数位dp P3188 [HNOI2007]梦幻岛宝珠-Solution

数位考虑+背包(+滚动数组)

首先，我们能发现，这是一道 \(n\) 很小但是体积和权值都非常大的背包。

但是这个题的体积有一个特殊的性质，就是他是 \(a\times 2^b,a\leq10\) 的形式，这个性质是非常好的。

我们定义 \(f_i\) 表示我们当前还剩 \(i\) 的空间我们能拿到的最大值，我们从大到小每个二进制位考虑过去。

因为 \(a\leq10\)，我们考虑之前的二进制位剩下的其实会有很多剩余。假如说我们这一位直接上 \(100\) 个物品，他也最多就 \(1000\) 个这个二进制位那么多体积的需求，所以超出这个需求的我们并不需要考虑，所以这样的话无形中就把体积降下来了。

上面这就是这题的主要思路，所以我们可以逐位二进制的背包，同时这题代码难度也是有点，还是对着题解看了一下才会写的。

#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N=5000;

typedef long long ll;
vector<pair<int,int> >item[40];
int n,W;
const ll inf=1ll<<60;
ll f[N],g[N];

void solve(){
    int s=0;
    for(int i=0;i<=30;++i) item[i].clear();
    for(int i=1;i<=n;++i){
        ll wei,val;
        read(wei,val);
        int pwei=__builtin_ctz(wei);
        wei>>=pwei;
        item[pwei].push_back(make_pair(wei,val));
        s+=wei;
    }
    for(int i=0;i<=s;++i) f[i]=-inf;
    f[0]=0;
    for(int i=30;i>=0;--i){
        for(int i=0;i<=s;++i) g[i]=f[i],f[i]=-inf;
        int d=(W>>i)&1;
        for(int i=0;i<=s;++i) f[min(i*2+d,s)]=max(f[min(i*2+d,s)],g[i]);
        for(int i=s-1;i>=0;--i) f[i]=max(f[i],f[i+1]);
        for(auto p:item[i])
            for(int j=p.first;j<=s;++j)
                f[j-p.first]=max(f[j-p.first],f[j]+p.second);
    }
    cout<<f[0]<<endl;
}

int main(){
    while(1){
        read(n,W);
        if(n==-1&&W==-1) break;
        solve();
    }
    return 0;
}