「HNOI 2007」梦幻岛宝珠

题目大意：

神仙DP。

$f[i][j]$ 表示体积为 $j \times 2^i$ 再加上 $w$ 二进制第 $i$ 位以下的体积最多可以获得多少价值。

#include <cstdio>
#include <cstring>
 
const int N = 1105;
 
int f[35][N], c[35], s[35], w[105][N], v[105][N];
 
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
int max(int x, int y) {
    return x > y ? x : y;
}
int min(int x, int y) {
    return x < y ? x : y;
}
 
int main() {
    while (1) {
        int n = read(), m = read(), mx = 0;
        if (n < 0) break;
        memset(f, 0, sizeof f);
        memset(c, 0, sizeof c); //表示第i层有几个物品
        memset(s, 0, sizeof s); //第i层物品的重量总和
        for (int i = 1; i <= n; ++i) {
            int x = read(), j = 0;
            while (!(x & 1)) ++j, x >>= 1;
            w[j][++c[j]] = x, s[j] += x, v[j][c[j]] = read();
            mx = max(mx, j);
        }
        for (int i = 0; i <= mx; ++i) //第i层
            for (int j = 1; j <= c[i]; ++j) //第j个物品
                for (int k = s[i]; k >= w[i][j]; --k) //装满容量为k的背包
                    f[i][k] = max(f[i][k], f[i][k-w[i][j]] + v[i][j]);
        while (m >> mx) ++mx; --mx; //2^mx<=m
        for (int i = 1; i <= mx; ++i) { //前i层
            s[i] += (s[i-1] + 1) >> 1; //前i层的体积之和为s[i]*2^i(上取整)
            for (int j = s[i]; ~j; --j) //装满容量为j的背包
                for (int k = 0; k <= j; ++k) //前i-1层的体积
                    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[mx][1]);
    }
    return 0;
}