E - 梦幻岛宝珠 HYSBZ - 1190 变形01背包 难

E - 梦幻岛宝珠

 HYSBZ - 1190 

这个题目我觉得很难，看题解都看了很久。

首先可以得到一个大概的思路就是分组，每一个数都可以分成 a*2^b  所以把b相同的数都分成一个组。

在每一组内部进行01背包，这个操作比较简单。

比较难的是组与组之间进行转移。

定义 dp[i][j] 表示在第i层容量为 j*2^i 的最大价值。

那么怎么从第 i-1 层转移到第 i 层呢？

因为到dp[i][j] 到第 i 层的容量为 第 i 层本身的容量+之前总容量 所以就是 j*2^i+w&((1<<i)-1)

假设第 i 层只用了 (j-k）*2^i  这么多的容量，那么第(i-1)层还可以多用 k*2^i 这么多的容量。

那这样子怎么转移呢？

假设是从dp[i-1][x] 转移过来 就是说 i-1 层用了 x*2^(i-1)  的容量

因为到底 i 层一共有 j*2^i+w&((1<<i)-1) 的容量，第 i 层用了 (j-k)*2^i 的容量

所以 x*2^(i-1)=j*2^i+w&((1<<i)-1)-(j-k)*2^i

解出 x=2*k+(w>>(i-1)&1)

所以转移方程为 dp[i][j]=max(dp[i][j],dp[i-1][2*k+(w>>(i-1)&1)])

因为一共只有n个宝石，如果这n个宝石放在了同一组，而且 a*2^b 的a 都为10  这个第二维最大也只有10*n

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <iostream>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1000 + 10;
typedef long long ll;
int dp[35][1010];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) && n != -1 && m != -1) {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            int w, val, a = 0;
            scanf("%d%d", &w, &val);
            while (w % 2 == 0) w /= 2, a++;
            for (int j = 1000; j >= w; j--) dp[a][j] = max(dp[a][j], dp[a][j - w] + val);
        }
        int w = m, up = 0;
        for (int i = w; i; i >>= 1) up++; up--;
        for (int i = 1; i <= up; i++) {
            for (int j = 1000; j >= 0; j--) {
                for (int k = 0; k <= j; k++) {
                    dp[i][j] = max(dp[i][j], dp[i][j - k] + dp[i - 1][min(1000, 2 * k + ((w >> (i - 1)) & 1))]);
                }
            }
        }
        printf("%d\n", dp[up][1]);
    }
    return 0;
}

View Code