题目大意：01背包，其中weight<=2^30,但是每个weight都能写成a*2^b的形式，其中a<=10,b<=30

直接背包肯定TLE+MLE

考虑到每个weight都能写成a*2^b的形式，显然我们要按照b分层来进行背包

令f[i][j]表示有j*2^i+(w&(1<

首先每层内部先做一个01背包

然后层与层之间再转移

从大到小枚举j 转移方程为f[i][j]=max{f[i][j],f[i][j-k]+f[i-1][min(k*2+((w>>i-1)&1),1000)]}

这个是怎么来的呢？我们首先枚举j，然后枚举同一层花销的空间j-k，那么我们在上一层所能选择的就是k*2+((w>>i-1)&1)

很难理解？来举个栗子吧- -

w=(1000100010)2,i=6,j=(111)2,k=1

那么我们将要更新的是(111100010)2，用来更新这个值的是(110000000)2

k=1,代表本层之间差1，上一层之间就差2

((w>>i-1)&1=1，代表上一层还可以选1(第6位上的1)

我们会在下一层选择(1100010)2的空间，而这个值恰好记录在f[5][3]上

还是理解不能的只能多看几遍这段话了= = 这题真他妈理性愉悦

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int n,w; long long f[40][1010],ans; int main() { int i,j,k,x; while(cin>>n>>w,n>0) { memset(f,0,sizeof f);ans=0; for(i=1;i<=n;i++) { int a=0,b=0; scanf("%d%d",&a,&x); while(~a&1) a>>=1,++b; for(j=1000;j>=a;j--) f[b][j]=max(f[b][j],f[b][j-a]+x); } for(i=0;i<=30;i++) for(j=1;j<=1000;j++) f[i][j]=max(f[i][j],f[i][j-1]); for(i=1;i<=min(1000,w);i++) ans=max(ans,f[0][i]); for(i=1;i<=30&&(1<
      
       >i);~j;j--) { for(k=0;k<=j;k++) f[i][j]=max(f[i][j],f[i][j-k]+f[i-1][min(k+k+((w>>i-1)&1),1000)]); ans=max(ans,f[i][j]); } cout<