P3188 [HNOI2007]梦幻岛宝珠 做题记录

给你 nn 颗宝石,每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石,保证总重量不超过 WW,且总价值最大,并输出最大的总价值。

1n1001\le n \le 1001W,wi,vi2301\le W,w_i,v_i \le 2^{30}

保证每个 wiw_i 能写成 a×2b (a,bN)a \times 2^b\space (a,b \in \mathbb N) 的形式,a10a \leq 10 , b30b \leq 30,且答案不超过 2302^{30}

不难发现,虽然数据范围很大,但是由于 wi=a×2bw_i=a\times 2^b1a101\le a\le 10。所以 bb 相同的 ww 同时除掉 2b2^b 之后的和很小,只有 10n10n。那么不难想到按照 bb 分组,每组物品单独做背包,最后合并。

那么设 fi,jf_{i,j} 表示所有 b=ib=i 的物品,背包容量为 j×2ij\times 2^i 时的最大收益。这部分可以在 O(300n)O(300n) 的时间之内预处理完。

考虑如何合并,设 totitot_i 表示 b=ib=i 的物品数量,用类似数位 dp 的思路,设 gi,jg_{i,j} 表示前 iibb,背包容量为 (m&((1<<i)1))+j×2i(m\&((1<<i)-1))+j\times 2^i(也就是 mm 的前 i1i-1 位加上额外的 jj2i2^i)时的最大收益。这样设计状态的好处在于可以处理低位向高位借 11 的情况,那么转移即为

gi,j+k=max(gi,j+k,fj+gi1,min(10l=0i1totl,2k+((m>>(i1))&1)))g_{i,j+k}=\max(g_{i,j+k},f_j+g_{i-1,\min(10\sum\limits_{l=0}^{i-1}tot_l,2k+((m>>(i-1))\&1))})

即枚举有多少个 2i2^i 被上一位借了。

这部分的时间复杂度为 O(3000n)O(3000n),总时间复杂度 O(4000n)O(4000n) 左右。

代码如下:

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int S=105,BS=30,MS=1005;

int n,m;
int tot[BS+5],vw[BS+5][S],vv[BS+5][S];
int f[BS+5][MS],g[BS+5][MS];

void slove()
{
	for(int i=0;i<=BS;i++) tot[i]=false;
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(int i=1;i<=n;i++)
	{
		int w,v;
		scanf("%d%d",&w,&v);
		int a=w,b=0;
		while(a&1^1) a>>=1,b++;
//		printf(">> %d %d %d\n",a,b,v);
		vw[b][++tot[b]]=a;
		vv[b][tot[b]]=v;
	}
	for(int i=0;i<=BS;i++)
	{
		for(int j=1;j<=tot[i];j++)
		{
			int w=vw[i][j],v=vv[i][j];
			for(int k=tot[i]*10;k>=w;k--) f[i][k]=max(f[i][k],f[i][k-w]+v);
		}
	}
	// for(int i=0;i<=10;i++)
	// {
		// for(int j=0;j<=20;j++) printf("%d ",f[i][j]);
		// printf("\n");
	// }
	for(int i=0;i<=tot[0]*10;i++) g[0][i]=f[0][i];
	int sm=tot[0];
	for(int i=1;i<=BS;i++)
	{
		sm+=tot[i];
		for(int j=0;j<=sm*10;j++)
		{
			for(int k=0;k<=j;k++)
			{
				g[i][j]=max(g[i][j],f[i][j-k]+g[i-1][min((sm-tot[i])*10,k*2+((m>>i-1)&1))]);
			}
		}
	}
	printf("%d\n",g[BS][m>>BS&1]);
}

int main()
{
	while(1)
	{
		scanf("%d%d",&n,&m);
		if(n==-1&&m==-1) break;
		slove();
	}
	return 0;
}