斜率优化略解
斜率优化在dp中是比较常见的优化方法
斜率优化算法最重要的一步，就是要将状态转移方程改写为y=kx+b的形式。而这一算法主要的难点就在于，对于一个复杂的状态转移方程，我们将哪些项将作为y，哪些项最为k和x，哪些项作为b。
我们以Luogu P3195 [HNOI2008]玩具装箱TOY为例来说斜率优化
在本题中，设前缀和为sum[i]，由题意易得dp方程：
[dp[i]=Min(dp[j]+(sum[i]+i-sum[j]-j-L-1)^2) (j<i)
]
(O(N^2))的，过不了此题
(b[i]=sum[i]+i+L+1)（这一步是为了简化计算）
则（先忽略Min）：
$$dp[i]=dp[j]+(a[i]-b[j])^2$$
展开得：
$$dp[i]=dp[j]+a[i]^2-2⋅a[i]⋅b[j]+b[j]^2$$
移项得（移的项实际比较套路）：
$$2⋅a[i]⋅b[j]+dp[i]−a[i]^2=dp[j]+b[j]^2$$
我们把这个方程转化成y=kx+b的形式：
(dp[j]+b[j]^2)是y,(2⋅a[i])是k（斜率）,(b[j])是x，(dp[i]-a[i]^2)是b（截距）
这个式子珂以变成平面直角坐标系上的一条一次函数
因为对于每个i来说，a[i]都是确定的
(a[i]^2)（一个定值）
而题目即为找这个截距的最小值
本题中可能为最优的P点组成了一个下凸包（其他题目可能不同，结合题目具体分析）
显然，凸包中相邻两点斜率是单调递增的
(2⋅a[i])也是单调递增的
(slope(P_j,P_{j+1}) > 2 cdot a[i])的点(slope(a,b)表示a，b两点连线的斜率)
(slope(P_j,P_{j+1}))
完整代码：
#include <bits/stdc++.h>
#define N 50005
#define db double
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register long long x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[35];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
int n,L;
db sum[N],dp[N];
int head,tail,q[N];
inline db a(register int i)
{
return sum[i]+i;
}
inline db b(register int i)
{
return a(i)+L+1;
}
inline db Y(register int i)
{
return dp[i]+b(i)*b(i);
}
inline db slope(register int i,register int j)
{
return (Y(i)-Y(j))/(b(i)-b(j));
}
int main()
{
n=read(),L=read();
head=tail=1;
for(register int i=1;i<=n;++i)
{
sum[i]=(db)read();
sum[i]+=sum[i-1];
while(head<tail&&slope(q[head],q[head+1])<a(i)*2)
++head;
dp[i]=dp[q[head]]+(a(i)-b(q[head]))*(a(i)-b(q[head]));
while(head<tail&&slope(i,q[tail-1])<slope(q[tail-1],q[tail]))
--tail;
q[++tail]=i;
}
write((long long)dp[n]);
return 0;
}