P3188

· · 个人记录

[HNOI2007]梦幻岛宝珠

输入 w_i,v_i 写反了结果调了半节晚自习都没调出来？

普通的 01 背包，但是数据很大，不过给了写特殊性质，w_i=a\times2^b 且 a\le 10。

然后很容易就可以想到按这个 b 来分组 DP，定义第 i 组的容量为 j\times 2^{(i-1)} 状态 f_i,_j。

然后转移很好搞：

f_i,_j=\max\{f_i,_{j-a_k}+v_k\}

最重要的是如何整合这几组状态。

反正肯定不能直接容量定义状态，那不如就照葫芦画瓢，同样按上面的分组转移。

定义状态 g_i,_j 表示选择到第 i 组，第 i 组的容量是 j\times 2^{(i-1)} 的最大价值。

显然我们不知道这个状态的定义到底有何意义，仍然没有合并的思路。

那么不加解释地给出转移方程：

g_i,_j=\max\{g_{i-1},_{2(j-p_k)+W_{i-2}}+f_i,_p\}

首先，我们知道，当前组的状态的费用乘上 2 其实就可以应用到上一组的状态再转移过来，这个很好想。但是为什么会加上 W_{i-2}（表示 W 的第 i-2 位，即第 i-1 组的背包容量），其实就是把背包容量累积下来加到最后的状态。这个还是比较巧妙的。

所以最后的 Ans=g_{cnt_w},_1。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e2;

ll n,W;

ll v[N+5],w[N+5],a[N+5];

ll f[40][N*40+5],g[40][N*40+5];

ll count(ll x) {
    ll res=0;while(x>0) {x>>=1;res++;}return res;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) { 
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    while(1) {
        memset(f,0,sizeof(f));memset(g,0,sizeof(g));
        n=read();W=read();
        if(n==-1&&W==-1) break;
        for(ll i=1;i<=n;i++) {
            w[i]=read();v[i]=read();
            ll tmp_lowbit=w[i]&(-w[i]);
            a[i]=w[i]/tmp_lowbit;
            ll tmp_pos=count(tmp_lowbit);
            for(ll j=400;j>=a[i];j--) {
                f[tmp_pos][j]=max(f[tmp_pos][j],f[tmp_pos][j-a[i]]+v[i]);
            }
        }
        ll tmp_cntw=count(W);
        for(ll i=1;i<=tmp_cntw;i++) {
            for(ll j=400;j>=0;j--) {
                for(ll k=0;k<=j;k++) {
                    g[i][j]=max(g[i][j],g[i-1][(j-k)*2+((W>>(i-2))&1)]+f[i][k]);
                }
            }
        }
        writeln(g[tmp_cntw][1]);
    }

    return 0;
}