昨天晚上肝了几道斜率优化的题，这里一起把题解写了吧。
BZOJ 1096
题目大意
有$n\le 10^6$个工厂，每个工厂的位置在$x_i$，有$p_i$个存货。
可以在工厂处建造仓库，在第$i$个工厂建造仓库的花费是$c_i$。
每个工厂的存货不能往编号小的仓库运东西。
一个单位货物运送一个单位长度需要一个花费。
求最小的总费用。
解析
考虑dp。
设$s1_i=\sum_{k\in[1,i]} p_k$，$s2_i=\sum_{k\in[1,i]} p_k\times x_k$，那么我们可以推出这个方程：
$$dp_i=min(dp_j + c_i + \sum_{k\in[j+1,i]}(x_i-x_j)\times p_j)=min(dp_j+c_i-(s2_i-s2_j)+x_i\times(s1_i-s1_j))$$
套路一波，假设$k$比$j$优秀（$k>j$），那么：
$$dp_k+c_i-(s2_i-s2_k)+x_i\times(s1_i-s1_k)<dp_j+c_i-(s2_i-s2_j)+x_i\times(s1_i-s1_j)$$
随便推一下式子，应该就可以发现：
$$dp_k-dp_j+s2_k-s2_j<x_i\times(s1_k-s1_j)$$
$$\frac{dp_k-dp_j+s2_k-s2_j}{s1_k-s1_j}<x_i$$
那么斜率就出来了，直接上套路板子就可以了。时间复杂度$O(n)$。
Code
1 | #define DREP(i, s, e) for(int i = s; i >= e ;i--) |
BZOJ 1911
题目大意
一个部队中有$n\le 10^6$个人，每个人的战斗力为$x_i$。
假设一坨人的战斗力总和为$x$，那么他们最终的战斗力为$ax^2+bx+c$。
一坨人的编号要连续，最大化最终的战斗力。
解析
设$s_i=\sum_{k\in[1,i]} x_k$，则：
$$dp_i=max(dp_j+a\times(s_i-s_j)^2+b\times(s_i-s_j)+c)$$
套路：
$$dp_k-dp_j<a\times(s_k-s_j)\times(2s_i-s_k-s_j)+b(s_k-s_j)$$
$$\frac{\frac{dp_k-dp_j}{s_k-s_j}-b}{a}+s_k+s_j<2s_i$$
然后上板子
Code
1 | #define DREP(i, s, e) for(int i = s; i >= e ;i--) |
BZOJ 4518
题目大意
由$n\le 3000$条路$L_i$，分成$m$天走，最小化每天走的路程的方差。
设方差为$v$，输出$v\times m^2$。
解析
我们设总路程为$sum$，第$i$天走的路程为$l_i$，那么我们推一下方差：
要最小化答案，只要最小化$W=\sum_{i\in[1,m]}l_i^2$就可以了。
设$dp_{i,cur}$表示已经$cur$天走了$i$段路的最小$W$，记$s_i=\sum_{k\in[1,m]}L_k$，我们可以写出如下方程：
$$dp_{i,cur}=min(dp_{j,cur-1}+(s_i-s_j)^2)$$
套路一波，设$a(x)=dp_{x,cur-1}$，然后设$k>j$比$j$优秀，那么：
$$a(k)+(s_i-s_k)^2<a(j)+(s_i-s_j)^2$$
$$a(k)-a(j)<(2s_i-s_j-s_k)\times(s_k-s_j)$$
$$\frac{a(k)-a(j)}{s_k-s_j}+s_j+s_k<2s_i$$
然后就可以套路上板子了。时间复杂度$O(n\times m)$。
Code
1 | #define DREP(i, s, e) for(int i = s; i >= e ;i--) |