石子（环形）合并问题_dp 动态规划

石子合并问题(第三章题目)

Time Limit:

2000MS

Memory Limit:

30000K

Description 在一个圆形操场的四周摆放 N 堆石子 (N≤100) ，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。编一程序，读入堆数 N 及每堆石子数 (≤100) 选择一种合并石子的方案，分别得到合并这 N 堆石子为一堆，可以得到的最大得分和最小得分 Input 输入包含多个例子。第一行为 N ，即石子堆的数目，以下一行为 N 个整形，分别代表每堆石子的数目。当 N=0 时，输入结束。 Output 对每个例子，输出其最小得分和最大得分，这两个数值以空格间隔开，每个例子占一行。 Sample Input 6 30 35 15 5 10 20 3 1 2 3333 6 3 4 5 6 7 8 0 Sample Output 275 475 3339 6671 84 125 Hint 无 Source 《计算机算法设计与分析》第三版习题 3-6

#include #include #include #include #define N 210 #define INF 0x3f3f3f3f #define max(a,b) (a)>(b)?(a):(b) #define min(a,b) (a)>(b)?(b):(a) using namespace std; int n; longa[N]; longres_min[N][N], res_max[N][N], s[N][N]; int main() { scanf("%d", &n); int i, j, k, l; for (i = 1; i <= n; i++) { scanf("%d", &a[i]); a[i + n] = a[i]; } long last = clock(); for (i = 1; i <= 2 * n - 1; i++) { longsum = 0; for (j = i; j <= 2 * n - 1; j++) { sum += a[j]; s[i][j] = sum; } } for (k = 2; k <= n; k++) { for (i = 1; i <= 2 * n - k+ 1; i++) { j = i + k - 1; res_max[i][j] = res_max[i + 1][j] + s[i][j]; res_min[i][j] = res_min[i + 1][j] + s[i][j]; for(l = i + 1; l < j; l++) { res_min[i][j] = min(res_min[i][j], res_min[i][l] + res_min[l + 1][j] + s[i][j]); res_max[i][j] = max(res_max[i][j], res_max[i][l] + res_max[l + 1][j] + s[i][j]); } } } long resmin = INF, resmax = -INF; for (i = 1; i <= n; i++) { resmin = min(resmin, res_min[i][i + n -1]); resmax = max(resmax, res_max[i][i + n -1]); } printf("%lld\n%lld\n", resmin,resmax); long cur = clock(); double tm = (double(cur) - last) / CLOCKS_PER_SEC; printf("时间:%lf\n", tm); return 0; }