[HNOI2008]玩具装箱TOY /【模板】斜率优化
一.题目简述
给定一组数列，要把他们分成几组，代每个区间[x, y]的代价是 \((y-x+\sum_{i=x}^ya[i]-L)^2\).
二.解题思路
这题转移的方程都告诉了，可是还是做不起。不过看样子是个DP题，那我们来推方程。
先把令人厌恶的\(\sum\)去掉，使用前缀和来代替。
\[
f[i]=min(f[j]+(i-j+sum[i]-sum[j]-1-L)^2)
\]
（其实可以先去掉min不看）先来手算一下复杂度为\(O(n^2)\)，数据范围没得玩。于是我们果断使用单调队...列。不行啊用不了啊喂！！由于有平方，混进去了一个混着\(i,j\)的项，不能用单调队列。此时隆重请出今天的主角：斜率优化
三.斜率优化
所谓斜率，就是\(y=kx+b\)中的k罢了，但是这个东西要怎么优化呢？先将整个式子化简，有了方便有如下两条
- A[i]=sum[i]+i;
- B[i]=A[i]+L+1;
那么原式可以化简为
\[
f[i]=f[j]+(i-j+sum[i]-sum[j]-1-L)^2;\\
f[i]=f[j]+(A[i]-B[j])^2\\
f[i]=f[j]+A[i]^2+B[j]^2-2*A[i]*B[j]\\
2*A[i]*B[j]+f[i]-A[i]^2=f[j]+B[j]^2;
\]
来考虑一下我们手里的条件与目标：\(A[i],B[j],f[j]\)，齐全，目标:\(f[i]\)。可以直接求出，而我们现在要做的是优化，即要以最快的速度找出一个或少量的j来推出f[i].
话题回到斜率，先决条件已充分，现在要找出斜率。我们是要用j推i，所以需要将i,j分开，这句话的数学体现为
\[
2*A[i]*x+f[i]-A[i]^2=y
\]
可以发现x,y都是只跟j有关的项，剩下的项全都是跟i有关的（上面那句话的意思就是这个）。有了这个式子就可以进行计算了，请想象:我手头有一个斜率为\(2*A[i]\)的直线，但是与y轴的交点未知，我可以令他过某些点(这些点都是之前算出来的\((B[j],f[j]+B[j]^2)\))，以此来计算出对应的交点以及f[i]，在题目的期望下要求f[i]最小。
\[
f[i]=b+A[i]^2
\]
b为与y轴交点坐标，\(A[i]^2\)为
常数，所以在这道题中斜线要尽量的靠下且靠右
四.数形结合
现在来形象一点。
根据上文所提，相当于找一个所谓“右下角”的点，最后找到的点体现出来的性质就应该是**他和左边的点的斜率<2*a[i]<他与右边点的斜率**，可以用这个来作为寻找的依据。
又有几点
- A[i]是单调递增的，所以在i之后的点必然只会选择i的决策点之后的点，所以在i之前的决策点可以删掉
- 围成的凸要尽量大，即新加入的点形成的斜率如果小于之前的形成的就可以代替了（这句还是看代码吧，解释的很麻烦）
（其实找点的时候可以二分）
五.CODE
#include<iostream>
#include<cstring>
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
#define m_for(i,a,b) for(int i=a;i<=b;++i)
#define ll long long
ll read(){
ll res=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')res=res*10+(ch-'0'),ch=getchar();
return res*f;
}
const int MAXN=500005;
ll n,l,c[MAXN],s[MAXN],f[MAXN];
inline ll make_y(int i){
return f[i]+(s[i]+i+l+1)*(s[i]+i+l+1);
}
inline ll make_x(int i){
return (s[i]+i+l+1);
}
inline ll make_k(int x,int y){
return (make_y(x)-make_y(y))/(make_x(x)-make_x(y));
}
int q[MAXN],head=1,tail=1;
int main(){
n=read();l=read();
m_for(i,1,n)s[i]=s[i-1]+(c[i]=read());
m_for(i,1,n){
ll ai=s[i]+i;
while(head<tail&&make_k(q[head],q[head+1])<2*ai)head++;
int j=q[head];
f[i]=f[j]+(s[i]-s[j]+i-j-1-l)*(s[i]-s[j]+i-j-1-l);
while(head<tail&&make_k(q[tail],q[tail-1])>make_k(i,q[tail-1]))tail--;
q[++tail]=i;
}
cout<<f[n];
}