斜率凸优化小结

前言

很久以前考了一道叫做"林克卡特树"的题目( 还记得被八省联考支配的恐惧吗？)
正解是用直线去切一个凸函数......
当时并不是很会。然而(APIO)讲课竟然讲了并且卧槽我竟然还听懂了。
所以就回来把这个坑给填了。

斜率凸优化

当遇到关于需要恰好选取(K)个的(DP)问题的时候，
一般做法就是在(DP)数组上再设一维。这样做时间代价是(O(n))的。
其实不如给每次选取加一个权值(C)。
那么每次选取就需要付出(C)的代价。所以(C)越大选的越少，(C)越小选的越多。
所以？二分(C)即可。时间代价变为(O(logn))。
形象的来说，对于(DP)数组，取(E)个时的答案(best(E))是一个上凸的。
所以我们用(f(x) = Cx)这条直线去切这个上凸包，直到(best(K)-KC)是最优的。
那么此时选取的个数就是题目所需的(K)个了。
下面给一张图(引用自cjfdf)：

例1：[APIO2014]序列分割

题目戳这里
可以发现，对于不在同一段的任意两个元素(a),(b)，都对答案有(ab)的贡献。
所以处理出前缀和(pre)。
那么转移：(f_{i,j} = max{f_{k,j-1} + pre_k * (pre_i - pre_k)})。
斜率优化不解释，复杂度(O(nK))，可以直接通过原题。
如果(K leq 200) 变为(K leq n)呢？直接斜率凸优化即可，复杂度(O(nlogK'))。
代码戳这里

例2：[八省联考2018]林克卡特树lct

题目戳这里
本质上就是要选择出(K+1)条不相交的路径使它们的权值和最大。
考虑树形(DP)。设(f_{u,j,0/1/2})分别表示(u)点的度数为(0/1/2)时的最优解。
定义(Ans_{u,j})表示(max{f_{u,j,0/1/2}})。
转移：
对于(f_{u,j,0})有：

(f_{u,j,0} = max{ f_{u,j-t,0} + Ans_{v,t} })

对于(f_{u,j,1})有：

(f_{u,j,1} = max{ f_{u,j-t,1} + Ans_{v,t}})
(f_{u,j,1} = max{ f_{u,j-t,0} + f_{v,t,1} + Edge_{u,v}})
(f_{u,j,1} = max{ f_{u,j-t-1,0} + f_{v,t,0} + Edge_{u,v}})

对于(f_{u,j,2})有：

(f_{u,j,2} = max{ f_{u,j-t,2} + Ans_{v,t}})
(f_{u,j,2} = max{ f_{u,j-t+1,1} + f_{v,t,1} + Edge_{u,v}})

上述转移复杂度(O(nK^2))，不够优秀。
发现对于表示选择个数的第二维(j) 可以进行斜率凸优化。
直接斜率凸优化即可，复杂度变为(O(nlogK'))。实现代码戳我。