正文

[HNOI2007]梦幻岛宝珠 「套路：分层 $DP$」

IP云
IP云V管理员/3 阅读
11/30
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

显然直接 \(01\) 背包会超时并且超空间

套路：分层 \(DP\)

「考虑将每个子结构看作一层（也就是包含了不止 \(1\) 个物品的信息），并且大层不会对小层造成影响，可以考虑先进行每一层的自我更新（即用当前层物品更新当前层答案），再进行层的合并，此时考虑低层对高层的影响」

正题

那么这题有一个特殊性质： \(V_i = a \times 2^b\)

b值大的物品不会影响零碎剩余的重量上限。

将物品按b值分阶段处理。

那么就是分层 \(DP\)

先通过普通的 \(01\) 背包更新当前层自身最优解

再进行层合并：

令 \(g_{i, j}\) 表示第 \(i\) 层，\(a\) 为 \(j\) 的最优解，\(f_{i, j}\) 表示第 \(i\) 层，\(a\) 为 \(j\)，并且再加上 \(V_{total}\) 的 \(1...i - 1\) 位的最优解

那么对于第 \(i\) 层，枚举当前 \(j\)

对于转移，枚举在自身层内消耗的空间 \((j - k) \times 2^i\)，那么还剩下 \(k \times 2^i + V_{total}\{1...i - 1\}\) 的空间，分配给上一层，那么可得转移方程为

（注：\(w_i\) 表示 \(V_{total}\) 第 \(i\) 位）

\[f_{i, j} = \max \{g_{i, j - k} + f_{i - 1, 2k + w_i}\}
\]

同时，\(g_{i, j}\) 可以通过由大到小枚举来消除

代码 
#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 30 + 10;

const int MAXM = 1000 + 10;

int N, M;

LL f[MAXN][MAXM]= {0};

int getnum () {

	int num = 0;

	char ch = getchar ();

	int isneg = 0;

	while (! isdigit (ch)) {

		if (ch == '-')

			isneg = 1;

		ch = getchar ();

	}

	while (isdigit (ch))

		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return isneg ? - num : num;

}

int main () {

	while (~ (N = getnum ())) {

		M = getnum ();

		memset (f, 0, sizeof (f));

		for (int i = 1; i <= N; i ++) {

			int vol = getnum (), value = getnum ();

			int b = 0;

			while (! (vol & 1))

				vol >>= 1, b ++;

			for (int j = 1000; j >= vol; j --)

				f[b][j] = max (f[b][j], f[b][j - vol] + value);

		}

		int xm = M, maxb = 0;

		while (xm)

			xm >>= 1, maxb ++;

		for (int i = 0; i <= maxb; i ++)

			for (int j = 0; j <= 1000; j ++)

				f[i][j] = max (f[i][j], f[i][j - 1]);

		LL ans = 0;

		for (int i = 1; i <= maxb; i ++)

			for (int j = min (1000, M >> i); j >= 0; j --) // 注意此处上限是 min (100, M >> i)，M >> i 保证不会将高位拿多了

				for (int k = 0; k <= j; k ++) {

					f[i][j] = max (f[i][j], f[i][j - k] + f[i - 1][min ((k << 1) + ((M >> (i - 1)) & 1), 1000)]);

					ans = max (ans, f[i][j]);

				}

		printf ("%lld\n", ans);

	}

	return 0;

}

/*

4 10

8 9

5 8

4 6

2 5

-1 -1

*/

/*

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

*/

相关阅读

目录[+]