首页 > 代码库 > HDU 3506 (环形石子合并)区间dp+四边形优化
HDU 3506 (环形石子合并)区间dp+四边形优化
Monkey Party
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 1699 Accepted Submission(s): 769
Problem Description
Far
away from our world, there is a banana forest. And many lovely monkeys
live there. One day, SDH(Song Da Hou), who is the king of banana forest,
decides to hold a big party to celebrate Crazy Bananas Day. But the
little monkeys don‘t know each other, so as the king, SDH must do
something.
Now there are n monkeys sitting in a circle, and each monkey has a making friends time. Also, each monkey has two neighbor. SDH wants to introduce them to each other, and the rules are:
1.every time, he can only introduce one monkey and one of this monkey‘s neighbor.
2.if he introduce A and B, then every monkey A already knows will know every monkey B already knows, and the total time for this introducing is the sum of the making friends time of all the monkeys A and B already knows;
3.each little monkey knows himself;
In order to begin the party and eat bananas as soon as possible, SDH want to know the mininal time he needs on introducing.
Now there are n monkeys sitting in a circle, and each monkey has a making friends time. Also, each monkey has two neighbor. SDH wants to introduce them to each other, and the rules are:
1.every time, he can only introduce one monkey and one of this monkey‘s neighbor.
2.if he introduce A and B, then every monkey A already knows will know every monkey B already knows, and the total time for this introducing is the sum of the making friends time of all the monkeys A and B already knows;
3.each little monkey knows himself;
In order to begin the party and eat bananas as soon as possible, SDH want to know the mininal time he needs on introducing.
Input
There
is several test cases. In each case, the first line is n(1 ≤ n ≤ 1000),
which is the number of monkeys. The next line contains n positive
integers(less than 1000), means the making friends time(in order, the
first one and the last one are neighbors). The input is end of file.
Output
For each case, you should print a line giving the mininal time SDH needs on introducing.
Sample Input
8
5 2 4 7 6 1 3 9
Sample Output
105
Author
PerfectCai
Source
2010 ACM-ICPC Multi-University Training Contest(7)——Host by HIT
首先题意说的好麻烦,英语渣表示这是smg,意思就是N只猴子围成一个小圈圈大家一开始只认识自己,猴王每次只能挑出两个人介绍他们认识,花费的时间为这两个的时间总和。定义如果介绍了A和B,那么A认识的人也将认识B认识的,这所要的时间是所有的A&&B认识的人的时间和,模拟下发现这就是一个环形石子合并问题。
对于环形我们将N的环化为2*N的直线处理,最后答案就是MIN{dp[i][i+N-1] | 1<=i<=N},N*2<=2000,传统做法会T,使用四边形优化。
对其优化内涵并不是很熟悉只知道这个定理但是看不太懂证明过程只能先记着了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define MAX 2005 5 LL dp[MAX][MAX]; 6 LL pre[MAX]={0}; 7 int s[MAX][MAX]; 8 int a[MAX]; 9 const LL inf=999999999; 10 int main() 11 { 12 int N,m,i,j,k; 13 while(scanf("%d",&N)!=EOF){m=N*2; 14 for(i=1;i<=N;++i) scanf("%d",&a[i]),a[i+N]=a[i]; 15 for(i=1;i<=m;++i) 16 { 17 pre[i]=pre[i-1]+a[i]; 18 dp[i][i]=0; 19 s[i][i]=i; 20 } 21 for(int len=2;len<=m;++len) 22 { 23 for(i=1,j=len;j<=m;i++,j++) 24 {dp[i][j]=inf; 25 for(k=s[i][j-1];k<=s[i+1][j];++k) 26 { 27 28 LL t=dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]; 29 if(dp[i][j]>t){ 30 dp[i][j]=t; 31 s[i][j]=k; 32 } 33 } 34 } 35 } 36 LL ans=inf; 37 for(i=1;i<=N;++i) 38 if(ans>dp[i][i+N-1]) ans=dp[i][i+N-1]; 39 printf("%lld\n",ans); 40 } 41 return 0; 42 }
HDU 3506 (环形石子合并)区间dp+四边形优化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。