[HNOI2008]玩具装箱 （斜率优化入门）
先吐槽一波，为什么 latex 不能复制！！！！
好了让我们看看这道题。
设 sis_isi 为前 iii 个玩具的长度前缀和，设 fif_ifi 表示前 iii 个玩具的最小费用，于是有一个显然的转移方程：
fi=min{fj−1+(i−j+si−sj−1−L)2}f_i=min\{f_{j-1}+(i-j+s_i-s_{j-1}-L)^2\}fi=min{fj−1+(i−j+si−sj−1−L)2}
然后我们令 g(x)=sx+x−Lg(x)=s_x+x-Lg(x)=sx+x−L，t(x)=x+sx−1t(x)=x+s_{x-1}t(x)=x+sx−1
可以将转移方程化简为：
fi=min{fj−1+t(j)2−2g(i)t(j)}+g(i)2f_i=min\{f_{j-1}+t(j)^2-2g(i)t(j)\}+g(i)^2fi=min{fj−1+t(j)2−2g(i)t(j)}+g(i)2
好了，来到这里，要开始进入斜率优化了！
令 h(x)=fj−1+t(j)2h(x)=f_{j-1}+t(j)^2h(x)=fj−1+t(j)2
那么式子成为：
fi=min{h(j)−2g(i)t(j)}+g(i)2f_i=min\{h(j)-2g(i)t(j)\}+g(i)^2fi=min{h(j)−2g(i)t(j)}+g(i)2
我们做这一切完全是为了让式子好看一些（雾
既然叫优化，我们就不可能枚举每个点去转移，而是要快速得到决策点。
考虑 j1<j2j_1<j_2j1<j2，j2j_2j2 比 j1j_1j1 优的条件，注意下面中 t(j2)>t(j1)t(j_2)>t(j_1)t(j2)>t(j1)，因为 t(x)t(x)t(x) 单调增：
h(j1)−2g(i)t(j1)<h(j2)−2g(i)t(j2)⇒h(j2)−h(j1)<2g(i)(t(j2)−t(j1))⇒h(j2)−h(j1)t(j2)−t(j1)<2g(i)h(j_1)-2g(i)t(j_1)<h(j_2)-2g(i)t(j_2)\\\Rightarrow h(j_2)-h(j_1)<2g(i)(t(j_2)-t(j_1))\\\Rightarrow \frac{h(j_2)-h(j_1)}{t(j_2)-t(j_1)}<2g(i)h(j1)−2g(i)t(j1)<h(j2)−2g(i)t(j2)⇒h(j2)−h(j1)<2g(i)(t(j2)−t(j1))⇒t(j2)−t(j1)h(j2)−h(j1)<2g(i)
那部分是不是很像斜率的形式？所以称之为斜率优化。
记 T(j1,j2)=h(j2)−h(j1)t(j2)−t(j1)T(j_1,j_2)=\frac{h(j_2)-h(j_1)}{t(j_2)-t(j_1)}T(j1,j2)=t(j2)−t(j1)h(j2)−h(j1)
我们目前得到的结论：若j1<j2j_1<j_2j1<j2，T(j1,j2)<2g(i)T(j_1,j_2)<2g(i)T(j1,j2)<2g(i) 时，j2j_2j2 更优。
下面是两个重要的结论
队列中相邻点的斜率都大于 2g(i)2g(i)2g(i) 时，决策点为队首。
因为 T(j1,j2)>2g(i)T(j_1,j_2)>2g(i)T(j1,j2)>2g(i)，因此 j1j_1j1 优于 j2j_2j2，同理，j2j_2j2 优于 j3j_3j3，以此类推。
队列中相邻点斜率单调增
让我们考虑 j1<j2<j3j_1<j_2<j_3j1<j2<j3 这相邻三个点的情况：j2j_2j2 要成为决策点，就必须满足存在 g(i)g(i)g(i):
于是有 T(j1,j2)<2g(i)<T(j2,j3)T(j_1,j_2)<2g(i)<T(j_2,j_3)T(j1,j2)<2g(i)<T(j2,j3)，于是队列中斜率单调增。
知道了这个，就可以用一个单调队列来维护斜率了。
于是，我们用单调队列维护斜率单调增，同时队列中斜率都大于 2g(i)2g(i)2g(i)，每次决策点在队首。
由于每个点只进出队列一次，所以总复杂度 O(n)O(n)O(n)
#include
#define N 50005
using namespace std;
typedef long long LL;
LL z = 1, L, s[N], f[N];
int q[N], x = 1, y;
LL t(int x){
return s[x - 1] + x;
}
LL h(int x){
return f[x - 1] + t(x) * t(x);
}
LL g(int x){
return x + s[x] - L;
}
double T(int i, int j){
return 1.0 * (h(i) - h(j)) / (t(i) - t(j));
}
int main(){
int i, j, n, m;
scanf("%d%d", &n, &L);
for(i = 1; i <= n; i++) scanf("%d", &j), s[i] = s[i - 1] + j;
for(i = 1; i <= n; i++){
q[++y] = i;
while(x + 1 < y && T(q[y - 1], q[y]) < T(q[y - 2], q[y - 1])) q[y - 1] = q[y], y--;
while(x < y && T(q[x], q[x + 1]) < 2 * g(i)) x++;
f[i] = f[q[x] - 1] + (g(i) - t(q[x])) * (g(i) - t(q[x]));
}
printf("%lld", f[n]);
return 0;
}
作者：iamhpp
