merge.cpp

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

#include <iostream.h>
#include <fstream.h>
#include <math.h>


    void main()
    {
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int i,j,k,temp;
    int  stone_num;//石头堆数

    long int  stone_value[102];//存储每堆石头的石子个数
    //long int mark_max[102][102];//将列数堆石子合并成一堆的最大得分和
    fin>>stone_num;//读出石子堆数
	for( i=1;i<=stone_num;i++)//读出每堆石头的石子个数
	fin>>stone_value[i];
	fin.close();//关闭输入文件
	
	temp=stone_num+1; //辅助开辟数组空间，不用下标包含[0]的这种空间
    int **mark_max=new int *[temp];
          for (i=0;i<temp;i++)
          mark_max[i]=new int[temp];
    //long int mark_min[102][102];//将列数堆石子合并成一堆的最小得分和
    int **mark_min=new int *[temp];
          for (i=0;i<temp;i++)
          mark_min[i]=new int[temp];
	
    //特殊值：对每一堆石子来说，它的max和c的值
    for( i=1;i<=stone_num;i++)
    {
    mark_max[i][1]=0;
    mark_min[i][1]=0;
    }
    //初始值：含有两堆石子的stone_num个子序列的合并方案

    for( j=2;j<=stone_num;j++)
    for( i=1;i<=stone_num;i++)
    {
    long int total=0;//存储从第i个石子堆开始，顺序数j堆的石子总数
    for(int s=1;s<=j;s++)
    {
    int temp2=(i+s-2)%stone_num+1;
    total+=stone_value[temp2];
    }
    //初始化值
    mark_max[i][j]=0;
    mark_min[i][j]=100000000;

    for( k=1;k<=(j-1);k++)
    {
    int x=(i+k-1)%stone_num+1;//第i堆数起，顺时针数k+1堆的堆序列
    //处理最大得分合并的情况
    if(mark_max[i][j]<(mark_max[i][k]+mark_max[x][j-k]+total))
    {
    mark_max[i][j]=mark_max[i][k]+mark_max[x][j-k]+total;
    }
    //处理最小得分合并的情况
    if(mark_min[i][j]>(mark_min[i][k]+mark_min[x][j-k]+total))
    {
    mark_min[i][j]=mark_min[i][k]+mark_min[x][j-k]+total;
    }
    }
    }
    long int max_num=0;//定义一个初值
    long int min_num=100000000; //定义一个初值
    //在子序列（1，stone_num）,(1，stone_num),...,(1，stone_num)
    //中，选择得分总和最优的一个子序列。
    for( i=1;i<=stone_num;i++)
    {
    if (max_num<mark_max[i][stone_num])
       max_num=mark_max[i][stone_num];
    if (min_num>mark_min[i][stone_num])
       min_num=mark_min[i][stone_num];
    }
	fout<<min_num<<endl; //输出最小得分结果
	fout<<max_num<<endl; //输出最大得分结果
	
	//释放二维数组分配空间
    for ( i=0;i<temp;i++)
    delete []mark_max[i];
    delete []mark_max;
     mark_max=0;
    for ( i=0;i<temp;i++)
    delete []mark_min[i];
    delete []mark_min;
     mark_min=0;
    }