[HNOI2007]夢幻島寶珠

LCVI.[HNOI2007]夢幻島寶珠

好題。

明顯它是01背包的模型，但值域過大。咋辦呢？

我們考慮令 \(f_{i,j}\) 表示隻考慮 \(a\times 2^i\) 類型的物品，關于 \(a\) 做的一個背包。顯然，暴力求出這個東西的時空複雜度都是可接受的。

我們再考慮 \(g_{i,j}\) 表示有 \(j\times2^i+w\operatorname{and}(2^i-1)\) 這麼多的背包容量時的答案，即隻考慮 \(w\) 的下 \(i\) 位，且第 \(i\) 位上選了 \(j\) 機關的物品。我們考慮由 \(g_{i,j}\) 更新 \(g_{i+1}\)。

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,int> >v[40];
int f[40][2000],lim[40],g[40][2000];
void chmx(int &x,int y){if(x<y)x=y;}
int main(){
	while(true){
		scanf("%d%d",&n,&m);
		if(n==-1&&m==-1)break;
		memset(f,0,sizeof(f)),memset(g,0,sizeof(g)),memset(lim,0,sizeof(lim));
		for(int i=0;i<=30;i++)v[i].clear();
		for(int i=1,a,b,c;i<=n;i++){
			scanf("%d%d",&a,&b),c=0;
			while(!(a&1))a>>=1,c++;
			v[c].push_back(make_pair(a,b));
		}
		for(int i=0;i<=30;i++){
			for(auto k:v[i]){
				for(int j=lim[i];j>=0;j--)chmx(f[i][j+k.first],f[i][j]+k.second);
				lim[i]+=k.first;
//				printf("(%d,%d)\n",k.first,k.second);
			}
//			for(int j=0;j<=lim[i];j++)printf("%d ",f[i][j]);puts("");
		}
		for(int i=0;i<=lim[0];i++)g[0][i]=f[0][i];
		for(int i=0;i<=30;i++){
			for(int j=0;j<=lim[i];j++)for(int k=lim[i+1];k>=0;k--)chmx(g[i+1][k+((j+!((m>>i)&1))>>1)],f[i+1][k]+g[i][j]);
			lim[i+1]+=(lim[i]+!((m>>i)&1))>>1;
		}
		printf("%d\n",g[31][0]);
	}
	return 0;
}