bzoj1190 [HNOI2007]梦幻岛宝珠背包

题目

https://lydsy.com/JudgeOnline/problem.php?id=1190

题解

好神仙的一道题啊。

既然 \(w_i = a_i\cdot 2^{b_i}\)，那么不妨按照 \(b_i\) 来分组，每一组内部先做一个 01 背包，记为 \(f[i][j]\)。

然后考虑怎么求出最后的总答案。

下面就是很妙的部分了：

\(dp[i][j]\) 表示前 \(i\) 位中，容量 \(\leq j\cdot 2^i+(W\&(2^i-1))\) 的最大价值。

转移的时候我们枚举给 \(i-1\) 及以下的位多少容量，如果给了 \(k\)，那么实际上下一位获得的就是 \(2k + W_{i-1}\)，\(W_i\) 表示 \(W\) 的第 \(i-1\) 位。于是直接从 \(dp[i-1][2k+W_{i-1}]+f[i][j-k]\) 转移就可以了。

这个方法妙就妙在，发现我们不容易直接合并出 \(W\) 的限制，但是发现如果要合并出 \(W\)，需要知道的是对于每一个 \(i\)，某个在那一维上的容量 \(j\cdot 2^i\) 加上关于 \(W\) 在后面的位的情况，而这个东西可以进一步下去求。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const int N = 100 + 7;

const int M = 31 + 3;

int n, w;

int siz[M], dp[M][N * 10];

pii v[M][N];

inline void work() {

	memset(dp, 0, sizeof(dp));

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

		int len = siz[k], mm = 10 * n;

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

			for (int j = mm; j >= v[k][i].fi; --j)

				smax(dp[k][j], dp[k][j - v[k][i].fi] + v[k][i].se);

		if (k == 0) continue;

		for (int i = mm; ~i; --i)

			for (int j = 0; j <= i; ++j) smax(dp[k][i], dp[k][i - j] + dp[k - 1][std::min(mm, (j << 1) + ((w >> (k - 1)) & 1))]);

	}

	printf("%d\n", dp[31][0]);

}

inline void init() {

	memset(siz, 0, sizeof(siz));

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

		int c, a, b = 0;

		read(a), read(c);

		while (!(a & 1)) a >>= 1, ++b;

		v[b][++siz[b]] = pii(a, c);

	}

}

int main() {

#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

#endif

	while (read(n), read(w), ~n && ~w) {

		init();

		work();

	}

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj1190 [HNOI2007]梦幻岛宝珠背包

题目

题解

最新文章

热门文章

巴特西

bzoj1190 [HNOI2007]梦幻岛宝珠 背包

题目

题解

最新文章

热门文章

bzoj1190 [HNOI2007]梦幻岛宝珠背包