[HNOI2007]梦幻岛宝珠

DP 背包

题面

给你$n$颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过$m$，且总价值最大。

• $n\leq100,m\leq2^{30},val_i=a*2^b,a\leq10,b\leq30$

解析

既然都告诉了重量是$2$的幂次方带系数，那我们就可以用系数来代表一种重量。
就可以设状态为$f[i][j]$表示只取重量形如$a2^i$的物品，系数和小于等于$j$的最大价值
（因为系数转移起点可以大于$0$）。
然后可以在各个$i$内跑背包。

接下来考虑合并$i$不同的状态。
注意到一个问题，$i$从小往大转移时，$j$是会缩水的，因为$j/2$会强制向下取整。

假定$f[i-1]$系列对$f[i]$系列的系数贡献为$k$。
此时，如果二进制中$m$的第$i-1$位为$1$，说明对应的$f[i-1]$系列中的$j$可以是$k*2+1$。否则就只能是$k*2$。
这两个值$/2$后都是$k$，但是$f[i-1][k*2+1]\geq f[i-1][k*2]$。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=5e5+100;
int n,m,f[35][1010],V[35][1010],mx,t[35],W[35][1010];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int max(re int x,re int y){return x>y?x:y;}
il void init()
{
  mx=0;
  memset(f,0,sizeof(f));memset(V,0,sizeof(V));
  memset(W,0,sizeof(W));memset(t,0,sizeof(t));
}
int main()
{
  while(233)
    {
      n=gi();m=gi();
      if(n==-1&&m==-1) break;
      init();
      fp(i,1,n)
    {
      re int x=gi(),y=gi(),j=0;
      while(!(x&1)) {x>>=1;++j;}
      mx=max(mx,j);
      t[j]+=x;
      V[j][++V[j][0]]=x;//volume
      W[j][++W[j][0]]=y;//val
    }
      fp(i,0,mx)
    fp(j,1,V[i][0])
    fq(k,t[i],V[i][j])
    f[i][k]=max(f[i][k],f[i][k-V[i][j]]+W[i][j]);
      while(m>>mx) ++mx;--mx;
      fp(i,1,mx)
      {
    t[i]+=(t[i-1]+1)/2;
    fq(j,t[i],0)
    fp(k,0,j)
      f[i][j]=max(f[i][j],f[i][j-k]+f[i-1][min(t[i-1],(k<<1)|((m>>i-1)&1))]);
      }
      printf("%d\n",f[mx][1]);
    }
  return 0;
}