main.cpp

在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆

#include <iostream>
#include <string> 
#define  N     500 
#define  oo    2000000000 
#define  MIN(a, b) (a)<(b)?(a):(b)
#define  MAX(a, b) (a)>(b)?(a):(b) 
using namespace std;
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堆的石子总数 

// 递归打印子序列f[i][j]的合并过程 
void Print(int i, int j)                              
{
    int k, x;
    if(j != 1) {
        Print(i, f[i][j].d);                            
        x = (i + f[i][j].d - 1)%n + 1;
        Print(x, j - f[i][j].d);                      
        
        for(k = 1; k <= n; k++)               
            if(v[k] > 0)
            {
                if(i == k || x == k) cout<<"*"<<v[k]<<" ";   // *号表示这次操作合并该堆 
                else cout<<v[k]<<" "; 
            }
        cout<<endl;
        v[i] = v[i] + v[x];                          
        v[x] = -v[x];                                 // 置为"-" 类似于删除 
    }    
}


// flag = 0求最小得分, flag = 1 求最大得分 
void Solve(int flag)                              
{
    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;               
    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;                                  
        }
    

    cout<<(flag == 0 ? "最小" : "最大")<<"得分是 "<<result<<endl;

	cout<<"合并过程如下:"<<endl;
    Print(k, n);                                   
	cout<<sum[1][n]<<endl;
}
     
int main()
{
		int i, j;
		cout<<"输入石子堆数："<<endl;
		cin>>n; 
		cout<<"输入每堆石子数："<<endl;
        for(i = 1; i <= n; i++) cin>>v[i];
        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]));  
        Solve(1); 
    
    return 0;    
}