程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> BZOJ 1190 HNOI2007 夢幻島寶珠 動態規劃

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

編輯:關於C++

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved