[HNOI 2007] 梦幻岛宝珠

题目大意

给你 nn 颗宝石,每颗宝石都有重量和价值。从这些宝石中选取一些宝石,保证总重量不超过 WW,求最大的总价值。每颗宝石的重量可表示为 a×2ba \times 2^b。多组数据。

1T201 \leqslant T \leqslant 20

1n1001 \leqslant n \leqslant 100

1W2301 \leqslant W \leqslant 2^{30}

1a10,  1b301 \leqslant a \leqslant 10, \; 1 \leqslant b \leqslant 30

题目链接

【HNOI 2007】梦幻岛宝珠 - Luogu 3188

题解

数据范围很大但又有特殊性质(只是 aa 比较小而已)的 01 背包。

bb 分类求解多组 01 背包问题。最后再像 01 背包一样合并答案。

由于是按 bb 分类的,所以第 ii 组的重量 11 是第 i1i - 1 组的重量 22

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXB = 35;
const int MAXA = 15;
const int MAXN = 105;
int main() {
int n, m;
while (~scanf("%d %d", &n, &m) && n != -1 && m != -1) {
static int wei[MAXB][MAXA], val[MAXB][MAXA], W[MAXB], cnt[MAXB];
memset(W, 0, sizeof (W));
memset(cnt, 0, sizeof (cnt));
int pow = 0;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
int cpow = 0;
while (x % 2 == 0) x >>= 1, cpow++;
wei[cpow][++cnt[cpow]] = x;
W[cpow] += x;
scanf("%d", &val[cpow][cnt[cpow]]);
pow = std::max(pow, cpow);
}
static int f[MAXB][MAXA * MAXN];
memset(f, 0, sizeof (f));
for (int i = 0; i <= pow; i++) {
for (int j = 1; j <= cnt[i]; j++) for (int k = W[i]; k >= wei[i][j]; k--)
f[i][k] = std::max(f[i][k], f[i][k - wei[i][j]] + val[i][j]);
}
while (m >> pow) pow++;
pow--;
for (int i = 1; i <= pow; i++) {
W[i] += (W[i - 1] + 1) / 2;
for (int j = W[i]; ~j; j--) for (int k = 0; k <= j; k++)
f[i][j] = std::max(f[i][j], f[i][j - k] + f[i - 1][std::min(W[i - 1], (k << 1) | ((m >> (i - 1)) & 1))]);
}
printf("%d\n", f[pow][1]);
}
return 0;
}