自动搬运

查看原文

来自洛谷，原作者为

	Felix72 公式和原理永远无法推论人情。

搬运于2025-08-24 23:08:40，当前版本为作者最后更新于2025-01-21 16:45:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

拿金币的后效性太大了，我们完全分析不出一个保证最优的贪心策略。如果你做过 [ARC098F] Donation 或者偶然注意到了样例分析中 Uolevi 不可能收集到大于 6 个金币，因为边缘所有格子的承受能力都小于等于 5 这句话，你就会想到倒推。

我们假设最后有 $k$ 个金币，你从边上的一个格子出发，在满足重量限制的情况下可以随意走动，并可以在没有放过金币的格子放下一枚金币，如果 $k$ 个金币都能放下就是合法。显然，遵从能放就放的贪心策略是不劣的。

你发现答案可以二分了。二分完 $k$ 之后，如果你知道从哪个格子结束，那么通过用堆找可达的 $d_{x, y}$ 最大的没放过金币的格子 $(x, y)$，内层可以 $O(k \log k)$ 检验合法性。但是遗憾的是我们并不知道从哪个格子结束，如果全部枚举一遍就会超时。

此时我们需要知道，冰面上的移动并非无迹可寻，令相邻的两个格子 $(x_1, y_1), (x_2, y_2)$ 之间有一条权值为 $\min(d_{x_1, y_1}, d_{x_2, y_2})$ 的边，那么原来点的重量限制就转化为边的重量限制。把最大生成树建出来，你发现只需要保留这些边就够了。

因此我们在二分内层对 kruskal 重构树进行 DP，设 $f_p$ 表示 $p$ 的子树可以随便走时，你最少剩下多少金币。初始条件是若 $p$ 是叶子节点且对应原图的边界上的点，还要满足 $k \leq d_{p_x, p_y}$，那么 $f_p = k - 1$（当前位置就能先放下一个），否则 $f_p = \infin$。转移也简单，如果一个非叶子结点 $p$ 满足 $f_{ls_p} \leq lim_p$（$lim_p$ 是 $p$ 对应的边的重量限制），那么 $f_p = \min(f_p, f_{ls_p} - (siz_p - siz_{ls_p}))$，意思是满足了 $p$ 的重量限制，那么右子树自然可以随便走了。对右子树的转移同理。

如果 $f_{root} \leq 0$，说明可以放完，此时 $k$ 合法。

DP 部分：

int lim[N * 2], f[N * 2], siz[N * 2], ls[N * 2], rs[N * 2];
inline void treedp(int pos, int x)
{
	if(is[pos] && x <= lim[pos]) f[pos] = x - 1;
	if(ls[pos] && rs[pos])
	{
		treedp(ls[pos], x), treedp(rs[pos], x);
		siz[pos] = siz[ls[pos]] + siz[rs[pos]];
		if(f[ls[pos]] <= lim[pos]) f[pos] = min(f[pos], f[ls[pos]] - (siz[pos] - siz[ls[pos]]));
		if(f[rs[pos]] <= lim[pos]) f[pos] = min(f[pos], f[rs[pos]] - (siz[pos] - siz[rs[pos]]));
	}
	else siz[pos] = 1;
}
inline bool check(int x)
{
	memset(f, 0x3f, sizeof(f));
	memset(siz, 0, sizeof(siz));
	treedp(dsu.idx, x);
	return (f[dsu.idx] <= 0);
}