BZOJ 1190 HNOI2007 夢幻島寶珠 動態規劃

BZOJ 1190 HNOI2007 夢幻島寶珠 動態規劃

題目大意：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<