P3188
Zwaire
·
·
题解
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$ $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$ 而不是正好是当前的体积，和背包的思想类似
细节标注在代码里，所以考虑问题考虑全面，以防出现我这发现不了的错误。
```c++
/*
所以，走过的坑大家不要再犯
*/
#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。感谢在讨论区和评论区指正的各位！~~