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