参考博文: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