题解：P11303 [NOISG2021 Finals] Pond

· · 题解

这不是去年正睿某天 T4 吗？后面忘了，反正是道 DP 好题就是了。

首先 O(k(n-k)) 的 DP 是容易的，直接关路灯即可，但是优化不了一点。

但是我们关路灯用了费用提前计算的思想，这题也可以呢，只不过我们之前的贡献思想基于每步操作两侧路灯的贡献，自然需要二维来知道两边的信息，我们能否只用关系一侧信息？

不妨设每个点下标为 p，考虑除了从 k 走向 i 的那段是一定会有的之外其他所有背道而驰的路径都会使得这个水藻产生额外的贡献，如果从左边 i 走到右边 j 此时对 1\sim i-1 的额外的贡献就是 2(i-1)\times (p_j-p_i)，为什么有二倍呢？因为你过去了还要回来，这也是额外的代价啊。相反同理。

设 f_i 为当前走到了 i 的最小代价转移有：

\begin{aligned} &f_i+2(p_j-p_i)\times(i-1)\to f_j,i\leq K,j\geq K\\ &f_i+2(p_i-p_j)\times(n-i)\to f_j,i\geq K,j\leq K \end{aligned}

这个转移有环，但是我们可以从最短路的角度看不难发现可以 dijkstra，每次从最小的开始转移，显然当前考虑完了的区间是 [l,r]，每次考虑 f_{l-1} 和 f_{r+1} 哪个更小即可，一开始 f_{K}=\sum\limits_{i=1}^{n}|p_K-p_i|，答案就是 \min(f_1,f_n)，看哪个先被转移到。

直接转移是 O(n^2) 的，但是这个 DP 显然可以斜率优化，所以可以维护凸包做到 O(n)。