bzoj1190:[HNOI2007]梦幻岛宝珠(分层背包DP)

Author Avatar
Sakits 3月 17, 2018

题解

  细节挺多的题,要彻底理解还是撕烤了挺久的qaq(可能是我太笨了…
  首先看到a2ba*2^b的要求就知道肯定要按bb分组了,这个我一眼还是看得出来的…这题还是难在转移的部分…
  先组内DP,设f(i,j)f(i,j)bbii的物品,容量为j2ij*2^i的最大收益,转移和普通背包DP一样就不说了。
  再组间DP,设f(i,j)f(i,j)bib\leq i的物品,容量为j2i+(m&(2i1))j*2^i+(m\& (2^i-1))的最大收益,则有:

f(i,j)=max(f(i,jk)+f(i1,2k+(m&2i1))f(i,j)=max(f(i,j-k)+f(i-1,2k+(m\& 2^{i-1}))

  可以优化一下枚举的范围,设did_i为第ii组需要枚举的jj,则有di=di+di1+12d_i=d_i+\frac{d_{i-1}+1}{2}
  因为nn只有100100,所以did_i不会超过10001000,复杂度显然是对的。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=110, inf=1e9;
int n, m, w, v, mx;
int cnt[40], d[40], a[40][maxn], b[40][maxn], f[40][1010];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
} 
inline int min(int a, int b){return a<b?a:b;}
int main()
{
	read(n); read(m);
	while(n!=-1 && m!=-1)
	{
		memset(f, 0, sizeof(f));
		memset(cnt, 0, sizeof(cnt));
		memset(d, 0, sizeof(d)); mx=0;
		for(int i=1;i<=n;i++)
		{
			read(w); read(v);
			int pos=0; while((w&1)==0) w>>=1, pos++;
			mx=max(mx, pos);
			d[pos]+=w; a[pos][++cnt[pos]]=w; b[pos][cnt[pos]]=v;
		}
		for(int i=0;i<=mx;i++)
		{
			for(int j=1;j<=cnt[i];j++)
			{
				for(int k=d[i];k>=a[i][j];k--)
				f[i][k]=max(f[i][k], f[i][k-a[i][j]]+b[i][j]);
			}
		}
		mx=0; while(m>>mx) mx++; mx--;
		for(int i=1;i<=mx;i++)
		{
			d[i]+=(d[i-1]+1)>>1;
			for(int j=d[i];j>=0;j--)
			{
				for(int k=0;k<=j;k++)
				f[i][j]=max(f[i][j], f[i][j-k]+f[i-1][min(d[i-1], k<<1|((m>>(i-1))&1))]);
			}
		}
		printf("%d\n", f[mx][1]);
		read(n); read(m);
	}
}