石子合并问题（完整）.cpp

经典石子合并问题全代码 在一个园形操场的四周摆放N堆石子（N≤100）

#include <stdio.h>
#include <string.h> 
#define   N      500 
#define   oo     2000000000 
#define   MIN(a, b) (a)<(b)?(a):(b)
#define   MAX(a, b) (a)>(b)?(a):(b) 
typedef struct { int c, d; } Node;    
int n;
int v[N];                                               // 每堆石头的个数
int save[N];                                          // 输出最优解的具体合并需要随时改变 v 的值，所以为了同时输出最小，最大的合并，在完成一个任务之后需要回溯 
Node f[N][N];                                       // f[i][j]存储最优解，同时存储合并线索 
int sum[N][N];                                      // sum[i][j] 表示从第 i 堆起，顺时针数j堆的石子总数 
void Print(int i, int j)                               // 递归打印子序列f[i][j]的合并过程 
{
     int k, x;
     if(j != 1) {
         Print(i, f[i][j].d);                             // 倒推子序列 1 的合并过程
         x = (i + f[i][j].d - 1)%n + 1;
         Print(x, j - f[i][j].d);                        // 倒推子序列 2 的合并过程 
        
         for(k = 1; k <= n; k++)                  // 输出当前合并第i堆和第x堆的方案
             if(v[k] > 0)
             {
                 if(i == k || x == k) printf("-%d ", v[k]);    // -号表示这次操作合并该堆 
                 else printf("%d ", v[k]); 
             }
         printf("\n");
         v[i] = v[i] + v[x];                            // 新堆的大小 
         v[x] = -v[x];                                  // 置为"-" 类似于删除 
     }    
}
     
void Solve(int flag)                                 // flag = 0求最小得分, flag = 1 求最大得分 
{
     int i, j, k, x, t, result;
     for(i = 1; i <= n; i++)                         // 仅含一堆石子的序列不存在合并         f[i][1].c = f[i][1].d = 0;  
    
     for(j = 2; j <= n; j++) {                      // 顺推含2堆，3堆...n堆石子的各子序列的合并方案 
         for(i = 1; i <= n; i++) {
             t = sum[i][j];
             if(flag == 0) f[i][j].c = oo;           // 求最小得分，那么需要初始化为 oo 
             else           f[i][j].c = 0;                // 求最大得分，那么需要初始化为 0 
            
             for(k = 1; k <= j-1; k++) {
                 x = (i + k - 1)%n + 1;
                 if((flag == 0 && f[i][k].c + f[x][j-k].c + t < f[i][j].c)
                 ||(flag != 0 && f[i][k].c + f[x][j-k].c + t > f[i][j].c)) {
                     f[i][j].c = f[i][k].c + f[x][j-k].c + t;
                     f[i][j].d = k; 
                 }
             }    
         }
     }
    
     result = f[1][n].c; k = 1;                   // 在子序列f[1][n], f[2][n]...f[n][n]中寻找最优值 
     for(i = 2; i <= n; i++)
         if((flag == 0 && f[i][n].c < result) || (flag != 0 && f[i][n].c > result))
         {
             result = f[i][n].c;
             k = i;                                      // 记录下 k 
         }
    
     printf("%s score is : %d\n", flag == 0 ? "min" : "max", result); 
     printf("合并过程如下：\n");
     Print(k, n);                                      // 由此 k 出发 倒推合并过程 
     printf("%d\n\n", sum[1][n]);             // 输出最后一次将石子合并成一堆的石子总数 
}
     
int main()
{
     int i, r, j, k, x, t; 
     while(scanf("%d", &n), n) {        
         for(i = 1; i <= n; i++) scanf("%d", &v[i]);
         //memset(sum, 0, sizeof(sum)); 
         memcpy(save+1, v+1, n*sizeof(v[1])); 
        
         for(i = 1; i <= n; i++) sum[i][1] = v[i];
         for(j = 2; j <= n; j++)
         for(i = 1; i <= n; i++)
             sum[i][j] = v[i] + sum[i%n+1][j-1];
            
         Solve(0);
         memcpy(v+1, save+1, n*sizeof(v[1]));     // 回溯 v以便求最大得分
         Solve(1); 
     }
     return 0;    
}