自动搬运

查看原文

来自洛谷，原作者为

	FstAutoMaton 淋着 / 雨 / 谢幕，任 / 他人 / 笑话。

搬运于2025-08-24 22:44:40，当前版本为作者最后更新于2025-08-20 12:00:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

[USACO23JAN] Mana Collection P

好题。

直接做很困难，考虑找一些性质。

注意到每次到一个点会将之前的权值全部取走，所以一个点贡献的权值只与其最后一次被经过的时间有关。

将最初每个点的权值设为查询时的时间乘以点权，那么就可以反向考虑，将计算得到的权值的最大值转化为计算失去的权值的最小值。

设 $f_{i,S}$ 表示当前在点 $i$，经过的点的集合为 $S$，设 $g_{i,j}$ 为 $i$ 走到 $j$ 的最短路，$v_S=\sum_{x\in S}a_x$。枚举上一个走到的点 $j$，有转移：

$$f_{i,S}=\min_{j\in S,i\neq j} f_{j,S\setminus\{i\}}+v_{S\setminus\{i\}}\times g_{j,i} $$

所以我们可以在 $\operatorname{O}(2^n\ n^2)$ 的时间复杂度内求出 $f$。

考虑求出 $f$ 后如何计算答案。对于一组询问 $\{s,e\}$，其答案为：

$$\max_{S}v_S\times s-f_{e,S}$$

将 $s$ 视为一个变量，上面这个式子其实就是求若干条直线在 $x=s$ 这个位置的截距的最大值，按照 $e$ 分类李超树快速查询即可。

时间复杂度 $\operatorname{O}(2^n\ n^2)$，由于答案可能很大，所以要注意一下 inf 的设置防止出现精度问题，当然也可以直接开 int128。

code