BZOJ1190:[HNOI2007]梦幻岛宝珠 dp

思路:

首先很显然注意到应该按照2的幂次分组dp.

我的想法乱七八糟,就不提了.

发一个详细的网址:http://blog.csdn.net/PoPoQQQ/article/details/43953609

顺便吐槽我太弱.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 110
struct cost{
    int a,b;
    inline void init(int x){
        b=0;
        for(;x%2==0;x>>=1)++b;
        a=x;
    }
};
cost c[N];int v[N];
 
long long f[31][1010];
 
#define Max(x,y) ((x)>(y)?(x):(y))
 
int main(){
    int n,w,x;
    register int i,j,k;
    while(scanf("%d%d",&n,&w)&&(n+w>0)){
        memset(f,0,sizeof f);
        for(i=1;i<=n;++i)scanf("%d%d",&x,&v[i]),c[i].init(x);
         
        for(i=1;i<=n;++i)for(j=min(1000,w>>c[i].b);j>=c[i].a;--j)f[c[i].b][j]=Max(f[c[i].b][j],f[c[i].b][j-c[i].a]+v[i]);
         
        for(i=0;i<=30;++i)for(j=1;j<=1000&&j<=(w>>i);++j)f[i][j]=Max(f[i][j],f[i][j-1]);
         
        int re=0;
        for(k=1;k<=30&&(1<<k)<=w;++k){
            for(j=min(1000,w>>k);j>=0;--j)
                for(i=0;i<=j;++i)
                    f[k][j]=Max(f[k][j],f[k][j-i]+f[k-1][min(2*i+((w>>(k-1))&1),1000)]),re=Max(re,f[k][j]);
        }
         
        printf("%d\n",re);
    }
     
    return 0;
}