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<map> #include<set> #include<ctime> #include<cstdio> #include<cstring> #include<vector> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int n,L,l,r; int c[50005],q[50005]; ll s[50005],f[50005],C; double slop(int j,int k) { return (f[k]-f[j]+(s[k]+C)*(s[k]+C)-(s[j]+C)*(s[j]+C))/(2.0*(s[k]-s[j])); } void dp() { l=1;r=0;q[++r]=0; for(int i=1;i<=n;i++) { while(l<r&&slop(q[l],q[l+1])<=s[i])l++; int t=q[l]; f[i]=f[t]+(s[i]-s[t]-C)*(s[i]-s[t]-C); while(l<r&&slop(q[r],i)<slop(q[r-1],q[r]))r--; q[++r]=i; } } int main() { n=read();L=read();C=L+1; for(int i=1;i<=n;i++)c[i]=read(); for(int i=1;i<=n;i++)s[i]=s[i-1]+c[i]; for(int i=1;i<=n;i++)s[i]+=i; dp(); printf("%lld\n",f[n]); return 0; }
原文：http://www.cnblogs.com/lishiyao/p/6480633.html
