ARC096F Sweet Alchemy 题解

ARC096F Sweet Alchemy

题意

• 有 $n$ 个物品，买一个第 $i$ 个物品需要花费 $m_i$ 元。
• 除了第一个物品外，第 $i$ 个物品有一个上级物品 $p_i(< i)$。
• 给定 $d$，设第 $i$ 个物品买了 $c_i$ 个，要求对于 $i(\in [2,n])$ 满足 $c_{p_i} \le c_i \le c_{p_i} + d$。
• 一共有 $x$ 元，问最多能买多少个物品。
• $n \le 50$，$x,d,m_i \le 10^9$。

题解

设 $v_i$ 表示 $i$ 的子树大小，$w_i$ 表示 $i$ 的子树内权值和，则原问题等价于：

有 $n$ 个物品和一个体积为 $x$ 的背包。

第 $i$ 个物品体积为 $w_i$ 价值为 $v_i$ 个数为 $c_i$。

求背包能装下的最大价值和。

$v_i \le n \le 50$，$x,c_i,w_i \le 10^9$。

这是一个经典的多重背包问题，但这里的背包体积和总价值都非常大，因此无论是以体积为状态还是以价值为状态的多重背包都行不通。

注意到物品个数和价值都很小，考虑从这个角度入手。

考虑 $i,j$ 满足 $\frac {w_i}{v_i} \le \frac {w_j}{v_j}$：

• 若 $i$ 拿了 $v_j$ 个，体积为 $w_iv_j$，价值为 $v_iv_j$。
• 若 $j$ 拿了 $v_i$ 个，体积为 $w_jv_i$，价值为 $v_iv_j$。

由于价值一样，但前者的体积更小，所以前者一定不劣。

因此按照 $\frac wv$ 从小到大排序后，我们可以每个物品拿 $n$ 个出来，剩下的一定是从前往后贪心的拿。

此时总价值不超过 $\mathcal O(n^3)$，于是再考虑以总价值为状态的多重背包，即设 $f_{i,j}$ 为考虑到第 $i$ 个物品，总价值为 $j$ 的最小体积。

单调队列优化是 $\mathcal O(n^4)$ 的，二进制拆分则是 $\mathcal O(n^4 \log n)$ 的，都可以接受，但后者更好写。

代码

const int N = 57;
int n, p[N], t;
vi e[N];
ll x, d, w[N], v[N], c[N];

void dfs(int x) {
	v[x] = 1;
	for (int y : e[x])
		dfs(y), v[x] += v[y], w[x] += w[y];
}

const ll inf = 1e18;
ll W[N<<3|1], V[N<<3|1], f[N*N*N], s, ans;

int main() {
	rd(n), rd(x, d, w[1]), p[1] = 1;
	for (int i = 2, f; i <= n; i++)
		rd(w[i]), rd(f), e[f].pb(i), p[i] = i, c[i] = d;
	dfs(1), c[1] = x / w[1] * v[1];
	sort(p + 1, p + n + 1, [&](int i, int j) {
		return w[i] * v[j] < w[j] * v[i];
	});
	for (int i = 1; i <= n; i++) {
		int p = ::p[i];
		ll c = min(::c[p], (ll)n);
		s += c * v[p];
		ll k = 0, x = 0;
		while (x + (1 << k) <= c)
			x += 1 << k, V[++t] = (1 << k) * v[p], W[t] = (1 << k) * w[p], ++k;
		if (c - x) V[++t] = (c - x) * v[p], W[t] = (c - x) * w[p];
	}
	for (int i = 1; i <= s; i++) f[i] = inf;
	for (int i = 1, k = 0; i <= t; k += V[i++])
		for (int j = k; ~j; j--)
			f[j+V[i]] = min(f[j+V[i]], f[j] + W[i]);
	for (int i = 0; i <= s; i++)
		if (f[i] <= x) {
			ll now = i, sum = f[i];
			for (int j = 1; j <= n; j++) {
				int p = ::p[j];
				ll c = min(::c[p] - min(::c[p], (ll)n), (x - sum) / w[p]);
				now += c * v[p], sum += c * w[p];
			}
			ans = max(ans, now);
		}
	print(ans);
	return 0;
}