题解 CF321E 【Ciel and Gondolas】

诶，这题虽然是决策单调性，但是没人证啊(虽然比较显然)。 那我就来简单证一下叭： 考虑四边形不等式，如果是最小值问题，那大概长这样： $$a\leq b<c\leq d$$ $$w(a,c)+w(b,d)\le w(a,d)+w(b,c)$$ 那么如果满足这个，就说明其满足最小值时的决策单调性。证明起来很简单，因为 $a\to d,b\to c$ 的转移的值要更大些，所以 $a\to c,b\to d$ 的转移会更优，据此可得 $f$ 有决策单调性。 考虑拿四边形不等式来证明。对于 $a\leq b<c\leq d$ 而言，记 $s(a,c)$ 表示矩阵中左上角为 $(a,a)$ 右下角为 $(c,c)$ 的这么一个矩阵中元素的和，那么 $$w(a,c)+w(b,d)=\frac{s(a,c)+s(b,d)}{2}$$ $$w(a,d)+w(b,c)=\frac{s(a,d)+s(b,c)}{2}$$ 注意到 $$s(a,d) = s(a,c)+s(b,d)-s(b,c)+s(a,b)+s(c,d)$$ 那么就显然 $$w(a,c)+w(b,d)\le w(a,d)+w(b,c)$$ 十分满足决策单调性（其实画出图来更显然，就是多了两块矩阵）。 这个东西可以用分治来做。因为每一层决策与本层无关，即 $k-1\to k$ 。于是就可以 `solve(l,r,ql,qr)` 表示 $l\sim r$ 是从区间 $(ql\sim qr)$ 转移过来的。那么每次取 $mid=\frac{l+r}{2}$，然后找出 $f_{mid}$ 对应的最优决策所在位置，这样就可以分治了。复杂度 $O(nk\log n)$ 。