题解 CF321E 【Ciel and Gondolas】

这里再讲一种比除了 $wqs$ 二分之外都要优的 $O(n^2)$ 做法（神奇的与 $k$ 无关）。 首先决策单调性不再证明了，直接考虑怎么实现。 考虑记录一下每个点的决策范围。发现设状态 $(n,k)$ 最优决策位置记作 $opt(n,k)$ 的话，一定有 $$ opt(n,k-1)\leq opt(n,k)\leq opt(n+1,k) $$ 那么可以这么写： ```cpp for j : 1 to k for i : n to 1 for p : opt(i, j - 1) to opt(i + 1, j) if [f(p, j - 1) < f(i, j)] opt(i, j) = p, f(i, j) := f(p, j - 1) ; ``` 这样做显然是对的。于是来考虑这么做的时间复杂度。 发现对于这个决策矩阵的每一条穿过 $opt(i,j)$ 和 $opt(i+1,j+1)$ 的斜线，每条斜线的代价是 $O(n)$ 的，原因是考虑斜线 $opt(i,j),opt(i+1,j+1)$ 这条斜线的决策来自于 $opt(i,j-1),opt(i+1,j)$ 这条斜线。那么也就是说，每个斜线的转移都是 $O(n)$ 的，共有 $O(n+k)$ 条斜线，所以复杂度 $O(n^2)$ 。 代码就不给了，这个伪代码写的还是很规整的吧？