时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
计算出将Ｎ堆石子合并成一堆的最小得分。
【输入】
第一行为一个正整数N (2≤Ｎ≤100)；
以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。
【输出】
一个正整数，即最小得分。
【输入样例】
7
13
7
8
16
21
4
18
【输出样例】
239
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. #include <algorithm> 5. #define INF 0x3f3f3f3f 6. using namespace std; 7. int f[101][101]; 8. int s[101]; 9. int n,i,j,k,x; 10. void print() 11. { 12. for(i=1;i<=n;i++){ 13. for(j=1;j<=n;j++) 14. printf("%10d ",f[i][j]); 15. printf("\n"); 16. } 17. printf("\n"); 18. } 19. int main() 20. { 21. memset(f,INF,sizeof(f)); 22. scanf("%d",&n); 23. for(i=1;i<=n;i++){ 24. scanf("%d",&x); 25. s[i]=s[i-1]+x; 26. f[i][i]=0; 27. } 28. for(i=n-1;i>=1;i--){ 29. for(j=i+1;j<=n;j++) 30. for(k=i;k<=j-1;k++) 31. f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]); 32. } 33. //print(); 34. printf("%d\n",f[1][n]); 35. return 0; 36. }
