题解：P9020 [USACO23JAN] Mana Collection P

· · 题解

[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