笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 CF321E 【Ciel and Gondolas】

posted on 2020-03-25 15:48:44 | under 题解 |

诶,这题虽然是决策单调性,但是没人证啊(虽然比较显然)。

那我就来简单证一下叭:

考虑四边形不等式,如果是最小值问题,那大概长这样:

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