在一个圆形操场的四周摆放着n堆石子现要将石子有次序地.doc

在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分，并分析算法的计算复杂性。#include #include #define N 500#define oo 2000000000#define MIN(a, b) (a)(b)?(a):(b)typedef struct int c, d; Node;int n;int vN; / 每堆石头的个数int saveN; / 输出最优解的具体合并需要随时改变 v 的值，所以为了同时输出最小，最大的合并，在完成一个任务之后需要回溯Node fNN; / fij存储最优解，同时存储合并线索int sumNN; / sumij 表示从第 i 堆起，顺时针数j堆的石子总数void Print(int i, int j) / 递归打印子序列fij的合并过程int k, x;if(j != 1) Print(i, fij.d); / 倒推子序列 1 的合并过程x = (i + fij.d - 1)%n + 1;Print(x, j - fij.d); / 倒推子序列 2 的合并过程for(k = 1; k 0)if(i = k | x = k) printf(-%d , vk); / -号表示这次操作合并该堆else printf(%d , vk);printf(n);vi = vi + vx; / 新堆的大小vx = -vx; / 置为- 类似于删除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+) / 顺推含2堆，3堆.n堆石子的各子序列的合并方案for(i = 1; i = n; i+) t = sumij;if(flag = 0) fij.c = oo; / 求最小得分，那么需要初始化为 ooelse fij.c = 0; / 求最大得分，那么需要初始化为 0for(k = 1; k = j-1; k+) x = (i + k - 1)%n + 1;if(flag = 0 & fik.c + fxj-k.c + t fij.c) fij.c = fik.c + fxj-k.c + t;fij.d = k;result = f1n.c; k = 1; / 在子序列f1n, f2n.fnn中寻找最优值for(i = 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+)sumij = vi + su