stone.cpp

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

#include <stdio.h>
#define  oo  20000000
    
int sumij(int i,int j,int v[100],int n)
{
	int k;
	int sum=v[i];
	for(k=1;k<j;k++)
		sum+=v[(i+k)%n];
	return sum;
}

int Solve(int n,int sum[100][101],int flag)              // flag = 0求最小得分, flag = 1 求最大得分
{
    int i, j, k, x,result;
	int f[100][101];							//从第 i 堆起，顺时针数j堆的石子合并的得分总数
    for(i = 0; i <n; i++)                        // 仅含一堆石子的序列不存在合并
        f[i][1]=0;  
    
    for(j = 2; j <= n; j++) 
	{                     // 顺推含2堆，3堆...n堆石子的各子序列的合并方案
        for(i = 0; i < n; i++) 
		{
            if(flag == 0) f[i][j] = oo;          // 求最小得分，那么需要初始化为 oo
            else          f[i][j] = 0;               // 求最大得分，那么需要初始化为 0
           
            for(k = 1; k <= j-1; k++) 
			{
                x = ((i + k - 1)%n + 1)%n;
                if((flag==0&&f[i][k]+f[x][j-k]+sum[i][j]<f[i][j])||(flag!=0&&f[i][k]+f[x][j-k]+sum[i][j]>f[i][j])) 
                    f[i][j] = f[i][k] + f[x][j-k] + sum[i][j];
            }   
        }
    }
   
    result = f[0][n];                 // 在子序列f[1][n], f[2][n]...f[n][n]中寻找最优值
    for(i = 1; i <n; i++)
        if((flag == 0 && f[i][n] < result) || (flag != 0 && f[i][n] > result))
            result = f[i][n];
	return result;
}


main()
{
	int n;				//堆数
	int v[100];        // 每堆石头的个数
	int sum[100][101];  // sum[i][j] 表示从第 i 堆起，顺时针数j堆的石子总数 
	int i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&v[i]);
	for(i=0;i<n;i++)
		for(j=1;j<=n;j++)
		{
			sum[i][j]=sumij(i,j,v,n);
		}
	printf("%d\n%d\n",Solve(n,sum,0),Solve(n,sum,1));
}