BZOJ1190【HNOI2007】梦幻岛宝珠 <分层DP>

Problem

【HNOI2007】梦幻岛宝珠

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

给你N颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过W，且总价值最大，输出最大的总价值。
数据范围：$N\le 100，W\le 2^{30}$，且保证每颗宝石的重量可以表示为$a\times 2^b$的形式（其中$a\le 10,b\le 30$）

Input

输入文件中包含多组数据。每组数据的格式如下：第一行是两个正整数$n$和$W$，$1\le n\le 100,1\le W\le 2^{30}$，分别表示宝石的数目和最多能带走的宝石重量。接下来的$n$行，每行有两个正整数$weight_i$和$value_i$，$1\le weight_i\le 2^{30}, 0\le value_i\le 2^{30}$，分别表示第i颗宝石的重量和价值，且保证$weight_i$能写成$a\times 2^b(1\le a\le 10,0\le b\le 30)$的形式。同一行的两个正整数之间用空格隔开。最后一组数据的后面有两个$-1$，表示文件的结束。这两个$-1$并不代表一组数据，你不需对这组数据输出结果。并且输入文件中数据的组数不超过$20$。

Output

对于输入的每组数据，输出一个整数$C$，表示小P最多能带走的宝石的总价值。每个结果整数$C$单独占一行，且保证$C$不会超过$2^{30}$。

Sample Input

4 10
8 9
5 8
4 6
2 5
4 13
8 9
5 8
4 6
2 5
16 75594681
393216 5533
2 77
32768 467
29360128 407840
112 68
24576 372
768 60
33554432 466099
16384 318
33554432 466090
2048 111
24576 350
9216 216
12582912 174768
16384 295
1024 76
-1 -1

Sample Output

14
19
1050650

标签：分层DP

Solution

$W$很大，不能直接搞。
而保证 $weight=a\times 2^b,\ a\le 10$
因而可以按$b$分层后背包。
分层后先层内DP出$f[i][j]$表示$2^i$层级内容量为$2^i\times j$的最大价值。
然后层间DP求最大值：$f[i][j] = max(f[i][j], f[i][k]+f[i-1][(j-k)\times2+(w>>i-1)\&1])$
详见代码。

Code

#include <bits/stdc++.h>
#define LOG 30
#define MAX_N 100
using namespace std;
int n, m, l, w[MAX_N+5][LOG+5], c[MAX_N+5][LOG], f[LOG+5][MAX_N+5], cnt[LOG+5], s[LOG+5];
int main() {
    while (scanf("%d%d", &n, &m) && ~n && ~m) {
        memset(cnt, 0, sizeof cnt), memset(s, 0, sizeof s), memset(f, 0, sizeof f), l = 0;
        while (n--) {
            int x;	scanf("%d", &x);
            int t = 0;	while (!(x&1)) t++, x >>= 1;
            w[t][++cnt[t]] = x, s[t] += x;
            l = max(l, t), scanf("%d", &c[t][cnt[t]]);
        }
        for (int i = 0; i <= l; i++) for (int j = 1; j <= cnt[i]; j++)
            for (int k = s[i]; k >= w[i][j]; k--) f[i][k] = max(f[i][k], f[i][k-w[i][j]]+c[i][j]);
        while (m >> l) l++;	l--;
        for (int i = 1; i <= l; i++) {
            s[i] += (s[i-1]+1)>>1;
            for (int j = s[i]; ~j; j--) for (int k = 0; k <= j; k++)
                f[i][j] = max(f[i][j], f[i][j-k]+f[i-1][min(s[i-1], (k<<1)|((m>>(i-1))&1))]);
        }
        printf("%d\n", f[l][1]);
    }
    return 0;
}