石子合并
来源:http://218.5.5.242:9018/JudgeOnline/problem.php?id=1295
[问题描述]
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小总得分。
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小总得分。
[编程任务]
对于给定n堆石子,编程计算合并成一堆的最小总得分。
对于给定n堆石子,编程计算合并成一堆的最小总得分。
[输入格式]
输入文件的第1 行是正整数n,1<=n<=1000,表示有n堆石子。
第2行为n个整数,分别表示每堆石子的个数。
输入文件的第1 行是正整数n,1<=n<=1000,表示有n堆石子。
第2行为n个整数,分别表示每堆石子的个数。
[输出格式]
对于每组输入数据,输出一行,为最小总得分。
对于每组输入数据,输出一行,为最小总得分。
输入输出样例:
输入unite.in |
输出unite.out
|
4
4 4 5 9
|
43
|
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<iostream> #include<cstring> using namespace std; int f[1001][1001]; int s[1001]; int n,i,j,k,l,x; int mn=0x7fffffff; int main() { cin>>n; for(i=1;i<=n;i++) { cin>>x; s[i]=s[i-1]+x; } for(i=n+1;i<=2*n;i++){ s[i]=s[i-n]+s[n];} memset(f,127/3,sizeof(f)); for(i=1;i<=2*n;i++)f[i][i]=0; for(l=1;l<=n;l++) for(i=1;i<=2*n-l;i++) { j=i+l; for(int k=i;k<j;k++) f[i][j]=min(f[i][k]+f[k+1][j]+s[j]-s[i-1],f[i][j]); } for(i=1;i<=n;i++) mn=min(mn,f[i][i+n-1]); cout<<mn; return 0; } |
Subscribe