大家好，欢迎来到IT知识分享网。
一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。Input
输入有多组测试数据。
每组第一行为n(n<=100)，表示有n堆石子，。
二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量ai（0<ai<=100）
Output每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。
Sample Input
3
1 2 3
Sample Output
9 11
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define inf (1LL << 25) #define rep(i,j,k) for(int i = (j); i <= (k); i++) #define rep__(i,j,k) for(int i = (j); i < (k); i++) #define per(i,j,k) for(int i = (j); i >= (k); i--) #define per__(i,j,k) for(int i = (j); i > (k); i--) const int N = 110; int sum[N]; int dpma[N][N]; int dpmi[N][N]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; while(cin >> n){ rep(i,1,n) rep(j,1,n){ dpma[i][j] = 0; dpmi[i][j] = inf; } int in; rep(i,1,n){ cin >> in; sum[i] = sum[i - 1] + in; } rep(i,1,n){ dpmi[i][i] = 0; //我这里直接从长度为2开始合并，然后遍历分区间 } rep(l,2,n){ //合并的区间长度 rep(i,1,n - l + 1){ //开始位置 int e = i + l - 1; //结束位置 rep(o,i,e - 1){ //分段位置 int v = sum[e] - sum[i - 1]; dpma[i][e] = max(dpma[i][e], dpma[i][o] + dpma[o + 1][e] + v); dpmi[i][e] = min(dpmi[i][e], dpmi[i][o] + dpmi[o + 1][e] + v); } } } cout << dpmi[1][n] << ' ' << dpma[1][n] << endl; } getchar();getchar(); return 0; }
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/32647.html
