凸优化相关
考虑到
因为要最小化 \(\sum\limits_{i=1}^{m}\frac{num_i}{k_i}\) 所以用调整法可以说明 \((\sum\limits_{i=1}^{m}k_i sum_i)\) 会取其上界 \(1\)，这就把 \(\{k\}\) 给安排了。
只需要最小化右式子。再用调整法可以说明 sum 里面应该是连续的，于是可以先对 \(s\) 排序，然后按顺序做一个 dp。这实际上就转化成了一个限制区间个数的区间分拆问题
WQS 二分，引入一个惩罚参数 lambda，将问题转化为：不限制分组数，但每多一组就要付出 lambda 的代价。可以看出惩罚参数越大分组越少，所以我们大概是要求一个适当大的惩罚参数使得分组的组数不超过 \(m\)。
这里的四边形不等式貌似不能直接套结论把 \(\sqrt{x}\) 剥掉直接考虑 \(x\)，因为这里就是要考虑 \(w(i,j) = dp[i-1] + \sqrt{(j-i)(pre_{j} - pre_{i})} + \lambda\) 这样的 \(w\) 取 min，而不带负号 sqrt 并非下凸而是上凸。
当然这里还是只需要考虑 \(\sqrt{(j-i)(pre_{j} - pre_{i})}\) 是否满足四边形不等式。
直观地理解的话，把 \(pre_j\) 替换成 \(j\)，于是 \(w\) 刚好到 \(j-i\)，一个凸性的临界点。然后 \(pre\) 可能会再稍微下凸一点，即考虑到 \(\Delta pre\) 单调不减，就让这个 \(w\) 变成下凸的了。
然后就是一个典型的区间分拆问题，这类问题 听说 只要把四边形不等式证出来了，则可推出 Monge 最短路关于 经过的边数 \(k\)（即拆分组数）有下凸性。
这题貌似没有说清楚能不能让 \(num_i=0\)，即某个区间为空，即只需要区间数 \(\le m\) 而非恰好 \(m\)。但看起来通过一点调整可以说明组数越多越好。所以关于组数应该是一个下凸的减函数。
四边形不等式、区间包含单调性、决策单调性¶
要讨论的是这样的一类问题
关于某些 \(w\) 满足四边形不等式的证明：
(i)
把不等式写出来后，由于实质上只是左端点交换了一下，只与左端点有关的或者只与右端点有关的并不会改变，两边长得一样的，可以消去；常量更加可以消去了。 for example, 有时候 \(w(i,j)\) 可能会被替换成 \(w'(i,j) = dp[i-1] + w(i,j)\)，然而 \(dp[i-1]\) 这一项只与左端点有关，所以其是否满足四边形不等式并不会被改变。还有就像是 \(\lambda(j-i+1)\) 这种可以被拆成左、右端点独立作用的也会被消去。
(ii)
通过一点小技巧，可以发现 \(i<i+1\le j < j+1\) for \(j=j_0,j_0+1\) 满足四边形不等式 \(\implies\) \(i<i+1\le j < j+2\) 满足四边形不等式，同理可以如此扩展左端点。所以可以只证明左端点相差 \(1\) 与右端点相差 \(1\) 的情况。
(iii)
对于显式的、可求二阶导的下凸函数 \(f\)，\(w(i,j) := f(j-i)\)，证明则不需要这么麻烦。稍微推导可以发现无非是要说明对于 \(a< b\le c< d\) at the same time \(a+d = b+c\)，which actually represent the length of the 4 mentioned intervals，we have \(f(b) + f(c) \le f(a)+f(d)\)。FYI, there's a special interpretation on "intersect \(\le\) include", which is "equal \(\le\) different"。这样的话其实就是要说明 \(f(b) - f(a) \le f(d) - f(c)\)，然而 \(b-a = d-c\)，从而就是要说明 \(f(a+\Delta) - f(a) \le f(c+\Delta) - f(c)\)。这几乎就是下凸性质的定义。
(iv)
ref 决策单调性优化 dp 学习笔记 | Exber's Blog 上述性质似乎可以扩展（但没有提供证明），如果 \(w(l,r)\) 满足区间包含单调性和四边形不等式，\(f(x)\) 为下凸函数，则： - \(f(w(l,r))\) 满足四边形不等式 - 如果 \(f(x)\) 单调不降（也就是没有触底反弹那一段），则 \(f(w(l,r))\) 还满足区间包含单调性
(v)
还有一些问题，在考虑四边形不等式进行代数运算时，不妨考虑对于三个区间 \([l_1,l_2],[l_2,r_1],[r_1,r_2]\) 分别设一些变量，这样代数证明会明显一点。比如说证明 $$ f(s_1+s_2) + f(s_2+s_3) \le f(s_1+s_2+s_3) + f(s_2) $$
#2157. 「POI2011 R1」避雷针 Lightning Conductor - 题目 - LibreOJ
注意中途运算时 sqrt 相关操作不能取整，反之则会破坏 \(-\sqrt{x}\) 的下凸性（比如说相邻两项点值一样斜率就直接为 0 了）。
对于区间划分型 dp，听说 恰经过 \(k\) 条边蒙日矩阵最短路关于 \(k\) 是下凸的。
洛谷题解质量有点差，很多都看不出和 wqs 二分有什么关系。 这样思考，设 \(g_x\) 是恰选中 \(x\) 条白边的最小权。那么 \(f(x) := g_x - \lambda x\) 就是给这 \(x\) 条白边的权值减去 \(\lambda\) 的惩罚代价后的权值，那么 \(g_x-\lambda x\) 的最小值在什么地方取到？这等价于提前给所有白边都减去 \(\lambda\)，然后跑 mst。这有什么意义呢？
考虑 \((need-1, g_{need-1})\) 和 \((need, g_{need})\)，当 \(\lambda\) 恰好等于这两个点的斜率时，如果能有下凸性，并且同取最小值的时候可以取 \(x\) 大的，这时候就会取到后面的那个作为最小值的 \(x\) 点（如果取到 \(>need\) 的其实同理可以往回取）。
当 \(\lambda\) 大于这两个点的斜率时，\(< need\) 的部分 比 大于等于 \(\ge need\) 的部分不优。
当 \(\lambda\) 大于这两个点的斜率时，\(< need\) 的部分 比 大于等于 \(\ge need\) 的部分更优。
所以二分这个惩罚代价，使得 \(p = \max\{pos : f(pos) = \min_{x}\{f(x)\}\}\) 位于 \(\ge need\) 部分，那么必然通过调整使得 \(f(need) = f(p)\)。
貌似有道更难一点的：P5633 最小度限制生成树 - 洛谷。