凸优化DP
简介
凸优化用于一类dp优化的问题
可以把一个$O(n)$的复杂度优化成$O(\log n)$
如果我们最后的dp数组在某一维上是凸壳就可以用凸壳来维护
在这种问题中我们如果不管这一维的影响可以很快地求出极值
我们就可以用凸优化的思想来操作
算法流程
假设我们的dp数组是$F(x)$并且满足$F(x)$的导数是单调函数
我们就可以对$F$函数进行一定的修改使得$F’(x)=F(x)+kx$函数的极值落在我们需要求的那一个点上
于是我们可以对斜率k进行二分，来求出最合适的那一个值
具体来说，这道题里面我们需要求的是树上k+1条点不相交路径的最大权值和
我们发现如果设$F(x)$表示选出x条不相交路径的最大权值，最后的F函数是一个上凸壳
然后我们就可以考虑二分出斜率的偏移量$w$
考虑它的实际意义，就是说每次多选出一条路径就需要加上额外的$w$代价，这样dp我们只需要记录最值和对应的路径条数就可以了
至于是要让路径条数最大化还是最小化因题而异
其实挺简单的算法，多做几道题就会了