首页 > 代码库 > HDU 3507 Print Article(斜率优化DP)
HDU 3507 Print Article(斜率优化DP)
题目链接
题意 : 一篇文章有n个单词,如果每行打印k个单词,那这行的花费是,问你怎么安排能够得到最小花费,输出最小花费。
思路 : 一开始想的简单了以为是背包,后来才知道是斜率优化DP,然后看了网上的资料,看得还挺懂的,不过我觉得如果以后真遇到斜率DP,要推起来肯定不简单。。。。。
网上资料1
网上资料2
1 #include <iostream> 2 #include <stdio.h> 3 4 using namespace std; 5 6 int q[500005],dp[500005],sum[500005] ; 7 int head,tail,m,n ; 8 9 // dp[i]= min{ dp[j]+M+(sum[i]-sum[j])^2 }; 10 int getDP(int i,int j) 11 { 12 return dp[j] + m + (sum[i]-sum[j]) * (sum[i]-sum[j]) ; 13 } 14 int getUP(int j,int k)//求yj-yk 15 { 16 return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]) ; 17 } 18 int getDOWM(int j,int k)//求xj-xk 19 { 20 return 2*sum[j]-2*sum[k] ; 21 } 22 23 int main() 24 { 25 while(~scanf("%d %d",&n,&m)) 26 { 27 for(int i = 1 ; i <= n ; i++) 28 scanf("%d",&sum[i]) ; 29 sum[0] = dp[0] = 0 ; 30 for(int i = 1 ; i <= n ; i++) 31 sum[i] += sum[i-1] ; 32 head = tail= 0 ; 33 q[tail++] = 0 ; 34 for(int i = 1 ; i <= n ; i++) 35 { 36 //如果满足g[j,k]=yj-jk/xj-xk<sum[i]代表这j的决策比k的决策要更优,所以k可以直接淘汰了。 37 while(head+1 < tail && getUP(q[head+1],q[head]) <= sum[i] * getDOWM(q[head+1],q[head])) 38 head++ ; 39 dp[i] = getDP(i,q[head]) ; 40 //g[i,j]<g[j,k],那么j点便永远不可能成为最优解,可以直接将它踢出我们的最优解集。 41 while(head+1 < tail && getUP(i,q[tail-1]) * getDOWM(q[tail-1],q[tail-2]) <= getUP(q[tail-1],q[tail-2]) * getDOWM(i,q[tail-1])) 42 tail-- ; 43 q[tail++] = i ; 44 } 45 printf("%d\n",dp[n]) ; 46 } 47 return 0; 48 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。