自动搬运

查看原文

来自洛谷，原作者为

	Zwaire 把一切不可能变为可能

搬运于2025-08-24 21:46:17，当前版本为作者最后更新于2021-08-09 12:10:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P3188 梦幻岛宝珠

Link

总体评价：

其实是一个非常好的（板子题），主要考察对于 01 背包的理解和对于二进制的应用以及状压 DP 的理解，综合性非常强，值得一做。

题目大意：

就是裸的 01 背包，但是它的体积和价值都很大，而且每一个 $w[i]$ 都保证能写成 $a * 2^b (a,b \in N)$ 的形式,并且 $a \leq10, b \leq 30$。

题目分析：

这不是板子题吗？？？然后敲了一个板子上去（内心充满期待），然而，紫题怎么会这么容易啊喂，结果 TLE 和 RE 击碎了我（水）好好打题的欲望。

当然，每一个题都有一个突破点，而这个题的突破点就是数据范围，看到 $w$ 的数据范围的时候，其实我内心是有一丝窃喜的，因为这个题不会像之前一样没有思路了。

当然，这个 $a * 2^b$ 其实并没有什么大的用处，因为把一个数转换成二进制之后，它一定可以表示成这样的形式。所以我们接着分析题目，$a \leq 10$ 才是最重要的条件，我们看到这么小的数据，在结合一点二进制的知识，我们可以想到就是 提示你要拆位，并且按照b来分组，$a$ 就是相当于是体积了。（重点）

我们已经有了这么一个性质，接着我们就可以设状态了，（显然）我们对于每一位进行考虑，设 $g[i][j]$ 为在 $b = i$ 的这一组中所选取体积为 $j$ 的最大值，根据 01 背包的dp转移，我们可以得到：

$$g[i][p] = \max(g[i][p], g[i][p - k[i][j]] + val[i][j]) $$

简单解释一下我 奇怪 的变量名：

$\bullet$ 其中 $g$ 数组是上面我所说的。

$\bullet$ $i$ 是我所枚举的 $b$。（即二进制下拆位的哪一位）

$\bullet$ $p$ 是我所枚举的在 $i$ 这一位的体积。

$\bullet$ $k$ 是我所预处理后的各个宝珠，$val$ 同理。

这时候我们很高兴，可以把这题切了！！

但是，我们好像忘了什么条件，我们的 $W$ 好像并不满足那个（可爱）的性质。。。（陷入沉思）

思考问题在哪里，目前我们已经得到了在每一位二进制上的答案，但是需要把 $W$ 用二进制的形式统计答案。但是假设 $W$ 在第 $i$ 位为1，答案并不是单纯的由 $i$ 位决定，因为可以分解在 $(i-1)$ 位，并且体积为2。所以就不能单纯的依靠每一位进行转移，所以需要另一个数组辅助我们。

可以把 $W$ 分解为最高位以及低位两个部分进行考虑转移。因为最高位的体积为1。 设 $f[i][j]$ 为在 $0 \thicksim i$ 组一共选取了 $j * 2^i$ 的上界并且转移 $W$ 在 $0 \thicksim {i-1}$ 位拥有的贡献的最大价值。这样的话 $f[s][1]$ 表示取到 $2^s$ 并且已经处理了前 $s-1$ 位的贡献的最大价值，把两部分的贡献合起来了。还是根据最后想要的答案设置dp状态。

然后我们开始思考怎么转移，我们从 $i - 1$ 状态转移到 $i$ 的状态的时候，枚举 $p$ 为当前 $i$ 这一组选取的体积，我们在 $i$ 的时候表示 $j - p$ 的体积的话，根据二进制下的表示，其实相当于在 $i - 1$ 的这一位选取 $(j - p) * 2$ 的体积，当然，我们转移的时候，根据 $f$ 数组的含义，还需要考虑对于 $W_{i-1}$ 的贡献进行考虑。这样就可以将第 $i-1$ 位的贡献，转移到 $i$ 位。解决了之前不能单独从某一位考虑的问题。

于是乎，我们就可以得出一个十分可爱（难看）的 dp 转移的式子：

$$f[i][j] = \max(f[i][j], f[i - 1][(j - p) * 2 + W_{i-1})] + g[i][p]) $$

$\bullet$ 其中 $i$，$j$ 是我所枚举的组数和总的体积。

$\bullet$ $p$ 是我当前的组数内所需要的体积，$(j - p) * 2$ 是上一位的状态对这一位造成的影响。

$\bullet$ $W_{i-1}$ 是我对应的上一位的 $W$ 所对应的体积，即二进制下第 $i - 1$ 位，$g[i][p]$ 就是我这一位选 $p$ 的价值了。

呼~，我们终于做完了，答案当然就是 $f[s][1]$ 了，$s$ 是 $W$ 所对应的二进制最高位数，表示取 $2^s$ 的上界体积并且转移了 $W$ 在前 $s-1$ 的贡献的最大价值。

说一下这个题的一些坑

我做这个题的时候真的是很困难，（因为我很菜），其中有非常多的细节需要处理。

$\bullet$ 需要开 long long。

$\bullet$ 一个数组大小的关键点，后面的体积是由 $max\{a_i\} * n$ 来确定的。所以取到上界为1000，之前的 500 没出问题可能是没有这种数据吧 。

$\bullet$ 注意这道题的$f,g$两个数组都是大的容量向小容量取的 $\max$ 而不是正好是当前的体积，和背包的思想类似

细节标注在代码里，所以考虑问题考虑全面，以防出现我这发现不了的错误。

/*
所以，走过的坑大家不要再犯
*/
#include<bits/stdc++.h>
#define il inline
#define int long long //不开ll见祖宗 

using namespace std;
const int N = 1e6 + 10;

vector<int> val[N], k[N];

il int re()
{
	int x = 0, p = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') p = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * p;
}

int n, W, s;
int f[50][5000], g[50][5000];//注意这里不要开太小！！！ 

void init()//多组数据 
{
	s = 0;
	memset(f, 0, sizeof(f));
	memset(g, 0, sizeof(g));
	for(int i = 0; i <= 50; ++i) val[i].clear(), k[i].clear();
}

signed main()
{
	while(1)
	{
		n = re(), W = re();
		if(n == -1) break;
		init();
		for(int i = 1; i <= n; ++i)//读入
		{
			int x = re(), y = re(), t = 0;
			while(((x >> t) & 1) == 0) t++;//记录每一个物品的二进制的表示 
			val[t].push_back(y);
			k[t].push_back((x >> t));
		}
		while((W >> s)) s++;//总的体积的位数 
        s--; //转换成了实际上位移的位数，更加符合含义，上面的s统计的是w一共几位
		for(int i = 0; i <= s; ++i)
		{
			if(k[i].size() == 0) continue;
			for(int j = 0; j <= k[i].size() - 1; ++j)
				for(int p = 1000; p >= k[i][j]; --p)//此处的上界是由max(a)*n确定的，故取上界1000
					g[i][p] = max(g[i][p], g[i][p - k[i][j]] + val[i][j]);//g数组更新答案 
		}	
		for(int i = 0; i <= s; ++i)
			for(int j = 1000; j >= 0; --j)
				for(int p = 0; p <= j; ++p) {
                    if(i == 0) f[i][j] = max(f[i][j], g[i][p]);
                    else f[i][j] = max(f[i][j], f[i - 1][(j - p) * 2 + ((W >> (i - 1)) & 1)] + g[i][p]);
                }
		printf("%lld\n", f[s][1]);
	}
    getchar(); getchar();
}
/*
1 10
8 9
-1 -1
*/

完结撒花✿✿ヽ(°▽°)ノ✿

---

Update 2025.1.18

时隔好多年来补坑，之前因为AFO一直没有管博客的问题，现在看到了觉得还是填一下BUG比较好，防止误导更多的人（话说我怎么成第一篇题解了）。修改了 $f$ 数组的含义，以及数组的上界等问题，也对于含义进行了更加详细的阐述。 感谢大佬们的指正，QWQ。感谢在讨论区和评论区指正的各位！~~