题解 CF321E 【Ciel and Gondolas】

皎月半洒花 · 2020-03-26 12:50:02 · 题解

这里再讲一种比除了 wqs 二分之外都要优的 O(n^2) 做法（神奇的与 k 无关）。

首先决策单调性不再证明了，直接考虑怎么实现。

考虑记录一下每个点的决策范围。发现设状态 (n,k) 最优决策位置记作 opt(n,k) 的话，一定有

那么可以这么写：

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) 。

代码就不给了，这个伪代码写的还是很规整的吧？