c++之路进阶——斜率优化形如DP[i]=f[j]+x[i](f[j]只与j变量有关)的问题(Print Article)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c++之路进阶——斜率优化形如DP[i]=f[j]+x[i](f[j]只与j变量有关)的问题(Print Article),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2575字,纯文字阅读大概需要4分钟。
内容图文
参考博文:http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html//讲的真的很好,像我这种弱渣都听懂了。真心点赞!!!
Print Article
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 7976 Accepted Submission(s): 2471
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost
M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.
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 6usingnamespace std; 7 8structget 9 { 10int n,m,sum[maxn],a[maxn],dp[maxn],q[maxn]; 11int getup(int j,int k){return dp[j]+sum[j]*sum[j]-dp[k]-sum[k]*sum[k];}//分子 12int getdown(int j,int k){return2*sum[j]-2*sum[k];}//分母 13int getdp(int i,int j) {return dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]);}//dp[i]14get() 15 { 16while (scanf("%d%d",&n,&m)==2) 17 { 18for(int i=1;i<=n;i++) scanf("%d",&sum[i]); 19 sum[0]=dp[0]=0; 20for(int i=1;i<=n;i++)sum[i]+=sum[i-1]; 21int t=0,w=1; 22for (int i=1;i<=n;i++) 23 { 24while (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]); 26while (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; 33int main() 34 { 35get; 36return0; 37 }
Presentation Error 这种错误你们见过么?我也是醉了!
原文:http://www.cnblogs.com/grhyxzc/p/5155506.html
内容总结
以上是互联网集市为您收集整理的c++之路进阶——斜率优化形如DP[i]=f[j]+x[i](f[j]只与j变量有关)的问题(Print Article)全部内容,希望文章能够帮你解决c++之路进阶——斜率优化形如DP[i]=f[j]+x[i](f[j]只与j变量有关)的问题(Print Article)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。