在一个圆形操场的四周摆放着n堆石子

1、2 堆石在一个圆形操场的四周摆放着 n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将 n 堆石子合并 成一堆的最小得分和最大得分，并分析算法的计算复杂性。#include #include #defineN 500#defineoo 2000000000#defineMIN(a, b) (a)(b)?(a):(b)typedef struct int c, d; Node;int n;int vN;/ 每堆石头的个数int saveN;/ 输出最优解的具体合并需要随时改变 v 的int sumNN;

2、值，所以为了同时输出最小，最大的合并，在完成一个任务之后需要回溯Node fNN;/ fij 存储最优解，同时存储合并线索/ sumij 表示从第 i 堆起，顺时针数 j 堆的-可编辑修改 -石子总数void Print(int i, int j)int k, x;if( j != 1) Print(i, fi j.d);x = (i + fi j.d - 1)%n + 1;Print(x, j - fi j.d);for(k = 1; k 0)if(i = k | x = k) printf(-%d , vk);else printf(%d , vk);printf(n);vi = vi +

3、 vx;vx = -vx;/ 递归打印子序列 fi j 的合并过程/ 倒推子序列 1 的合并过程/ 倒推子序列 2 的合并过程/ 输出当前合并第 i 堆和第 x 堆的方案/ - 号表示这次操作合并该堆/ 新堆的大小/ 置为 - 类似于删除void Solve(int flag)/ flag = 0 求最小得分 , flag = 1 求最大得分int i, j, k, x, t, result; for(i = 1; i = n; i+) fi1.c = fi1.d = 0;for( j = 2; j = n; j+) for(i = 1; i = n; i+) / 仅含一堆石子的序列不存在合并

4、/ 顺推含 2 堆， 3 堆 .n 堆石子的各子序列的合并方案t = sumi j;if(flag = 0) fij.c = oo;else fi j.c = 0;for(k = 1; k = j-1; k+) x = (i + k - 1)%n + 1;/ 求最小得分，那么需要初始化为 oo/ 求最大得分，那么需要初始化为 0if(flag = 0 & fik.c + fxj-k.c + t fij.c) fi j.c = fik.c + fxj-k.c + t;fi j.d = k;result = f1n.c; k = 1;/ 在子序列 f1n, f2n.fnn中寻找最优值for(i =

5、 2; i = n; i+)if(flag = 0 & fin.c result)result = fin.c;k = i; / 记录下 kprintf(%s score is : %dn, flag = 0 ? min : max, result);printf（ 合并过程如下： n）;Print(k, n);/ 由此 k 出发 倒推合并过程printf(%dnn, sum1n);/ 输出最后一次将石子合并成一堆的石子总数int main()int i, r, j, k, x, t;while(scanf(%d, &n), n) for(i = 1; i = n; i+) scanf(%d, &vi);/memset(sum, 0, sizeof(sum);memcpy(save+1, v+1, n*sizeof(v1);for(i = 1; i = n; i+) sumi1 = vi;for( j = 2; j = n; j+)for(i = 1; i = n; i+)sumi j = vi + sumi%n+1 j-1;Solve(0);memcpy(v+1, save+1, n*sizeof(v1);/ 回溯 v