dp[i]=min(dp[j]+(sum[i]-sum[j]+i-j-1-L)^2) (j<i) 令f[i]=sum[i]+i,c=1+l 则dp[i]=min(dp[j]+(f[i]-f[j]-c)^2) 1.证明决策单调性 假设在状态i处的k决策优与j决策，即 dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-f[j]-c)^2 则对于i后的所有状态t，要证明决策单调性 即dp[k]+(f[t]-f[k]-c)^2<=dp[j]+(f[t]-f[j]-c)^2 只要证 dp[k]+(f[i]+v-f[k]-c)^2<=dp[j]+(f[i]+v-f[j]-c)^2 只要证 dp[k]+(f[i]-f[k]-c)^2+2*v*(f[i]-f[k]-c)+v^2<=dp[j]+(f[i]-f[j]-c)^2+2*v*(f[i]-f[j]-c)+v^2 只要证 2*v*(f[i]-f[k]-c)<=2*v*(f[i]-f[j]-c) 即f[k]>=f[j]（显然） 证明完毕 2.求斜率方程 因为dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-f[j]-c)^2 展开 dp[k]+f[i]^2-2*f[i]*(f[k]+c)+(f[k]+c)^2<=dp[j]+f[i]^2-2*f[i]*(f[j]+c)+(f[j]+c)^2 即 dp[k]-2*f[i]*(f[k]+c)+(f[k]+c)^2<=dp[j]-2*f[i]*(f[j]+c)+(f[j]+c)^2 即(dp[k]+(f[k]+c)^2-dp[j]-(f[j]+c)^2)/2*(f[k]-f[j])<=f[i] f[i]是单调递增的，我们使用队列维护一个下凸壳，每次取出队头作为决策 加入决策i时，令队尾为q[r]，前一个为q[r-1] 满足斜率(q[r],i)<斜率(q[r-1],q[r])时，显然队尾是无效的，将其弹出
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 56789
ll n,l,s[maxn],dp[maxn];
int head,tail,q[maxn];
double slove(int k,int j)
{
return (dp[k]-dp[j]+(s[k]+l)*(s[k]+l)-(s[j]+l)*(s[j]+l))/(2.0*(s[k]-s[j]));
}
int main()
{
scanf("%lld%lld",&n,&l);
for(int i=1; i<=n; i++)
{
scanf("%lld",&s[i]);
s[i]+=s[i-1];
}
for(int i=1; i<=n; i++)s[i]+=i;
l++;
for(int i=1; i<=n; i++)
{
while(head<tail&&slove(q[head+1],q[head])<=s[i])
head++;
dp[i]=dp[q[head]]+(s[i]-s[q[head]]-l)*(s[i]-s[q[head]]-l);
while(head<tail&&slove(i,q[tail])<slove(q[tail],q[tail-1]))
tail--;
q[++tail]=i;
}
printf("%lld\n",dp[n]);
return 0;
}