E51【模板】斜率优化DP 打印文章

/*
这是100分代码 
f[i]表示打印第1至第i个单词的最小花费

f[i]=min(f[j]+(s[i]-s[j])^2+L)  (0<=j<i)
f[i]=min(f[j]+ s[i]^2+s[j]^2-2s[i]*s[j]+L ) (j<i)

f[j]+s[j]^2=2*s[i] *s[j] + f[i]-s[i]^2-L 
设 y[j]= f[j]+s[j]^2 , x[j]=2.0*s[j] ,k=s[i] ,b= f[i]-s[i]^2-L
得：y[j]=kx[j]+b
1、y[j]和x[j]是已计算好的，而且可选，
2、k是固定的， 
3、选择不一样的j能够使得b最小：即固定斜率，选过一个点，使得和y轴的截距最小。
b变小，也意味着f[i]变小。

重点问题：选什么点？ 

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=550000;
LL c[N],s[N],q[N],f[N];
double X(int j){return 2.0*s[j];}
double Y(int j){return 1.0*(f[j]+s[j]*s[j]);}
double slop(int j1,int j2){return X(j2)==X(j1)?1e18*( Y(j2)-Y(j1) ): ( Y(j2)-Y(j1) ) / ( X(j2)-X(j1) );}
int  main()
{
    LL L;int n;
	while(scanf("%d%lld", &n, &L)!=EOF)
	{
	    s[0]=0;for(int i=1;i<=n;i++) scanf("%lld", &c[i]),s[i]=s[i-1]+c[i];
	    int l=1,r=1;q[1]=0;
	    f[0]=0;
	    for(int i=1;i<=n;i++)
	    {
	        while( (l<r)&&( slop(q[l],q[l+1]) <= s[i]     ) ) l++;
	        f[i]=f[q[l]]+(s[i]-s[q[l]])*(s[i]-s[q[l]])+L;
	        while( (l<r)&&( slop(q[r-1],q[r]) >= slop(q[r],i) ) ) r--;
	        q[++r]=i;
	    }
	    printf("%lld\n",f[n]);
	}
    return  0;
}