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

Problem

【HNOI2007】梦幻岛宝珠

Description

给你N颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过W，且总价值最大，输出最大的总价值。
数据范围：，且保证每颗宝石的重量可以表示为的形式（其中）

Input

输入文件中包含多组数据。每组数据的格式如下：第一行是两个正整数和，，分别表示宝石的数目和最多能带走的宝石重量。接下来的行，每行有两个正整数和，，分别表示第i颗宝石的重量和价值，且保证能写成的形式。同一行的两个正整数之间用空格隔开。最后一组数据的后面有两个，表示文件的结束。这两个并不代表一组数据，你不需对这组数据输出结果。并且输入文件中数据的组数不超过。

Output

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

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

1
2
3

14
19
1050650

标签：分层DP

Solution

很大，不能直接搞。
而保证
因而可以按分层后背包。
分层后先层内DP出表示层级内容量为的最大价值。
然后层间DP求最大值：
详见代码。

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;
}