参考博文：http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html//讲的真的很好，像我这种弱渣都听懂了。真心点赞！！！
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 7976 Accepted Submission(s): 2471
2，假设队列中从头到尾已经有元素a b c。那么当d要入队的时候，我们维护队列的上凸性质，即如果g[d,c]<g[c,b]，那么就将c点删除。直到找到g[d,x]>=g[x,y]为止，并将d点加入在 该位置中。
3，求解时候，从队头开始，如果已有元素a b c，当i点要求解时，如果g[b,a]<sum[i]，那么说明b点比a点更优，a点可以排除，于是a出队。最后dp[i]=getDp(q[head])。
1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #define maxn 500100 5 6 using namespace std; 7 8 struct get 9 { 10 int n,m,sum[maxn],a[maxn],dp[maxn],q[maxn]; 11 int getup(int j,int k){return dp[j]+sum[j]*sum[j]-dp[k]-sum[k]*sum[k];}//分子 12 int getdown(int j,int k){return 2*sum[j]-2*sum[k];}//分母 13 int getdp(int i,int j) {return dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]);}//dp[i] 14 get() 15 { 16 while (scanf("%d%d",&n,&m)==2) 17 { 18 for(int i=1;i<=n;i++) scanf("%d",&sum[i]); 19 sum[0]=dp[0]=0; 20 for(int i=1;i<=n;i++)sum[i]+=sum[i-1]; 21 int t=0,w=1; 22 for (int i=1;i<=n;i++) 23 { 24 while (t+1<w&&sum[i]*getdown(q[t+1],q[t])>=getup(q[t+1],q[t])) t++;//维护队列 25 dp[i]=getdp(i,q[t]); 26 while (t+1<w&&getup(i,q[w-1])*getdown(q[w-1],q[w-2])<=getup(q[w-1],q[w-2])*getdown(i,q[w-1])) w--; 27 q[w++]=i; 28 } 29 printf("%d\n",dp[n]); 30 } 31 } 32 }get; 33 int main() 34 { 35 get; 36 return 0; 37 }
c++之路进阶——斜率优化形如DP[i]=f[j]+x[i]（f[j]只与j变量有关）的问题（Print Article）
原文：http://www.cnblogs.com/grhyxzc/p/5155506.html