E53 斜率优化DP [HNOI2008]玩具装箱

/*
这是100分代码 
f[i]表示包装好第1至第i个物品的最小花费（不一定只用一个包装盒，只要1-i包装好就行）

f[i]=min(f[j]+(sa[i]-sa[j]+i-(j+1)-L)^2) (j<i)
f[i]=min(f[j]+(sa[i]+i-sa[j]-j-1-L)^2) (j<i)
令s[i]=sa[i]+i,L=1+L
则f[i]=min(f[j]+(s[i]-s[j]-L)^2)

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

2*s[i]*s[j] +f[i]-s[i]^2-L^2+2*L*s[i]=f[j]+s[j]^2+2*L*s[j] 
kx + b = y
k=2*s[i],x=s[j],b=f[i]-s[i]^2-L^2+2*L*s[i]
y=f[j]+s[j]^2+2*L*s[j] 

*/ 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=55500;
LL a[N],s[N],f[N],L;
int q[N];
double X(int j){return 2.0*s[j];}
double Y(int j){return 1.0*(f[j]+s[j]*s[j]+2.0*L*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()
{
    int n;scanf("%d%lld",&n,&L);
    s[0]=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++) s[i]+=i;
    L++;
    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]]-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;
}
/*

第二种解释（不推荐）：
 
1.设 j1 < j2 < i ,且j2 比 j1 好，则：f[j1]+(s[i]-s[j1]-L)^2 > f[j2]+(s[i]-s[j2]-L)^2
展开:
f[j1]+(s[i]-L)^2-2*(s[i]-L)*s[j1]+s[j1]^2 > f[j2]+(s[i]-L)^2-2*(s[i]-L)*s[j2]+s[j2]^2
f[j1]-2*(s[i]-L)*s[j1]+s[j1]^2 > f[j2]-2*(s[i]-L)*s[j2]+s[j2]^2
f[j1]+s[j1]^2-2*(s[i]-L)*s[j1] > f[j2]+s[j2]^2-2*(s[i]-L)*s[j2]
[ (f[j1]+s[j1]^2) -(f[j2]+s[j2]^2)] >  2*(s[i]-L)*s[j1]-2*(s[i]-L)*s[j2]
[ (f[j1]+s[j1]^2) -(f[j2]+s[j2]^2)] >  2*(s[i]-L)*(s[j1]-s[j2])
因为 (s[j1]-s[j2])<0 
[ (f[j1]+s[j1]^2)-(f[j2]+s[j2]^2) ] /(s[j1]-s[j2]) <  2*(s[i]-L)
注意：因为 2*(s[i]-L) 会随着i增加越来越大 

结论1：j1<j2<i，且j2比j1好，j1和j2的斜率小于 i相关的固定值2*(s[i]-L) ，
因为这个固定值随i增加而增加，故j2可以永久淘汰j1。

结论2： 维护队列下凸
上凸删除队尾的理由分三种：
1、将来t>i给出的斜率大于队尾上凸两个斜率（即大于当前队列所有斜率），那么队头开始删除直到只有一个点
2、将来t>i给出的斜率介于队尾上凸两个斜率之间，则队尾q[r]比q[r-1]和i都差，也应该删除q[r]
3、将来t>i给出的斜率小于队尾上凸两个斜率，则q[r-1]比q[r]和i都好，可以删除q[r] 
在上凸的前提下，以上3种情况q[r]都无法是3点（q[r-1]、q[r]、i）中最优的，所以q[r] 可以删除 

最后遇到了：slop(q[r-1],q[r])>slop(q[r],i) , 保证了队列的相邻两点的斜率递
增所以加入i： q[++r]=i;


#include<bits/stdc++.h>//60分
using namespace std;
typedef long long LL;
LL a[55500],sa[55500],f[55500];
int main()
{
    LL L;int n;scanf("%d%lld",&n,&L);
    sa[0]=0;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),sa[i]=sa[i-1]+a[i];
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=(LL)1<<60;//f[i-1]+(a[i]-L)*(a[i]-L);
        for(int j=i-1;j>=0;j--)
        {
            f[i]=min(f[i],f[j]+(sa[i]-sa[j]+i-(j+1)-L)*(sa[i]-sa[j]+i-(j+1)-L));
        }
    }
    printf("%lld\n",f[n]);
    return 0;
} 

*/