shiziguiping.cpp

石子归并问题：在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由

#include <stdio.h>
#include <iostream.h>
#define MAXNUM 100
int number;         //石子堆数 (要求小于MAXNUM)
int stones[MAXNUM];    //每堆石子数 
#define MOD(I) (((I)+number) % number)   //MOD(I) 对下标I模number循环 

//sum[i][j]表示从第i堆到第j堆的石子数总和(stones[i]+stones[i+1]+...+stones[j])
//若i<j则下标循环(mod number)
int sum[MAXNUM][MAXNUM];

//max[i][j]表示从第i堆到第j堆的石子归并最优值 
//若i<j则下标循环(mod number)
int max[MAXNUM][MAXNUM];
int min[MAXNUM][MAXNUM];
//s[i][j]=k 表示从第i堆到第j堆的石子最优归并应分解为max[i][k-1]和max[k][j]两步 
//若i<j则下标循环(mod number)
int s[MAXNUM][MAXNUM];

int tem_i[MAXNUM];         //石子起始的中间量
int step[MAXNUM];       //合并过程的石子起始
int istep = 0;        //合并的步骤数
//动态规划求解结束 max[start][MOD(start-1)]是最大值
//s[i][j]=k包含动态规划过程信息,表示从第i堆到第j堆的
//石子最优归并应分解为max[i][k-1]和max[k][j]两步
void get_step(int start, int end)
{

        if (MOD(start+1) == end)
        {
            step[istep]=start;
   cout<<"step["<<istep<<"]="<<step[istep]<<endl;  //cky
            istep++;
            return;
        }
        int k = s[start][end];
        if (k == MOD(start+1))
        {
            get_step(MOD(start+1),end);
            step[istep] = start;
   cout<<"step["<<istep<<"]="<<step[istep]<<endl;  //cky
            istep++;
               return;
        }
        if (k == end)
        {
            get_step(start,MOD(end-1));
            step[istep] = MOD(end-1);
   cout<<"step["<<istep<<"]="<<step[istep]<<endl;  //cky
            istep++;
               return;
        }
        if (start < k)
        {
            get_step(start,MOD(k-1));
            get_step(k,end);
        }
        else
        {
            get_step(k,end);
            get_step(start,MOD(k-1));
        }
        return;
 }

int in(int start, int mid, int end)   
{
        if (start<=end)
        {
            if (start<=mid && mid<=end)
                return 1;
            else
                return 0;
        }
        else
        {
            if (end<mid && mid<start)
                return 0;
            else
                return 1;
        }
}

void print(int minus)
{
       int i;
        for (i=0; i<number; i++)
        {
            if (tem_i[i] != tem_i[MOD(i+1)])
            {
                if (in(tem_i[i],minus,MOD(tem_i[MOD(i+1)]-1)) 
                     || in(tem_i[i],MOD(minus+1),MOD(tem_i[MOD(i+1)]-1)) )
                {
                    printf("%d ", -sum[tem_i[i>[MOD(tem_i[MOD(i+1)]-1)]);
                }
                else
                {
                    printf("%d ", sum[tem_i[i>[MOD(tem_i[MOD(i+1)]-1)]);
                }
            }
        }
        printf("\n");
}

 

void main()
{
    int i,j,k;
    int tem_s,tem_max,tem_start,tem_min;
    int start, len; //用start表示序列的开始点，len表示序列的长度 
//输入数据 
    printf("Please Input Number:");
    scanf("%d", &number);
    printf("Please Input Data:");
    for (i=0; i<number; i++)
    {
        scanf("%d", &stones[i]);
    }
//输入数据结束 
    
//初始化sum[i][j]    
    for (i=0; i<number; i++)
    {
        sum[i][i] = stones[i];
    }
    for (start=0; start<number; start++)
    {
        for (len=2; len<=number; len++)
        {
            sum[start][MOD(start+len-1)] = 
                  sum[start][MOD(start+len-2)] + stones[MOD(start+len-1)];
        }
    }
//初始化sum[i][j]结束 
//用动态规划求解
    //初始化长度为1，2的子问题 
    for (i=0; i<number; i++)
    {
        s[i][i] = i;
        min[i][i] = 0;
        s[i][MOD(i+1)] = MOD(i+1);
        min[i][MOD(i+1)] = stones[i] + stones[MOD(i+1)];
    }
    //初始化结束

//求最小和
    for (i=0; i<number; i++)
    {
        s[i][i] = i;
        min[i][i] = 0;
        s[i][MOD(i+1)] = MOD(i+1);
        min[i][MOD(i+1)] = stones[i] + stones[MOD(i+1)];
    }
    //初始化结束
    for (len=3; len<=number; len++)
    {
       //求长度为len的子问题
        for (start=0; start<number; start++)
        {
            i = start;
            j = MOD(start+len-1);
              tem_s = s[i][MOD(i+len-2)];
              tem_min = min[start][MOD(tem_s-1)] + min[tem_s][j] + sum[start][j];
             s[start][j] = tem_s;
             min[start][j] = tem_min;
            while(tem_s != s[MOD(start+1)][j])
            {
                tem_s = MOD(tem_s+1);
    //取最小值
                if(tem_min > min[start][MOD(tem_s-1)] + min[tem_s][j] + sum[start][j])
                {
                    tem_min = min[start][MOD(tem_s-1)] + min[tem_s][j] + sum[start][j];
                    s[start][j] = tem_s;
                    min[start][j] = tem_min;
    // printf("MIN%d    ",tem_min);   //cky
                }
            }
        }
    }
    
    tem_start = 0;
    tem_min = min[0][number-1];
    for (start=1; start<number; start++)
    {
        if (min[start][start-1] < tem_min)   //取最小值
        {
            tem_start = start;
            tem_min = min[start][start-1];
        }
    }
// cout<<"M"<<tem_min<<endl;  //cky

    start = tem_start;
    printf("最小值:%d\n",tem_min);

    get_step(start,MOD(start-1));
    for (j=0; j<number; j++)
    {
        tem_i[j] = j;
    }
    print(step[0]);

    for (k=0; k<number-2; k++)
    {
        istep = MOD(step[k]+1);
        start = tem_i[istep];
        int itemp = tem_i[step[k>;
        while ((tem_i[istep] == start) && (istep != step[k]))
        {
            tem_i[istep] = itemp;
            istep = MOD(istep+1);
        }
        print(step[k+1]);
    }
    printf("%d\n",sum[0][number-1]);


//初始化sum[i][j]    
    for (i=0; i<number; i++)
    {
        sum[i][i] = stones[i];
    }
    for (start=0; start<number; start++)
    {
        for (len=2; len<=number; len++)
        {
            sum[start][MOD(start+len-1)] = 
                  sum[start][MOD(start+len-2)] + stones[MOD(start+len-1)];
        }
    }
//初始化sum[i][j]结束 

//for(i=0;i<istep;i++)step[i]=0;    //
istep=0;
//求最大和
//用动态规划求解
    //初始化长度为1，2的子问题 
    for (i=0; i<number; i++)
    {
        s[i][i] = i;
        max[i][i] = 0;
        s[i][MOD(i+1)] = MOD(i+1);
        max[i][MOD(i+1)] = stones[i] + stones[MOD(i+1)];
    }
    //初始化结束

//求最大和
    for (i=0; i<number; i++)
    {
        s[i][i] = i;
        max[i][i] = 0;
        s[i][MOD(i+1)] = MOD(i+1);
        max[i][MOD(i+1)] = stones[i] + stones[MOD(i+1)];
    }
    //初始化结束
    for (len=3; len<=number; len++)
    {
       //求长度为len的子问题
        for (start=0; start<number; start++)
        {
            i = start;
            j = MOD(start+len-1);
              tem_s = s[i][MOD(i+len-2)];
              tem_max = max[start][MOD(tem_s-1)] + max[tem_s][j] + sum[start][j];
             s[start][j] = tem_s;
             max[start][j] = tem_max;
            while(tem_s != s[MOD(start+1)][j])
            {
                tem_s = MOD(tem_s+1);
    //取最大值
                if(tem_max < max[start][MOD(tem_s-1)] + max[tem_s][j] + sum[start][j])
                {
                    tem_max = max[start][MOD(tem_s-1)] + max[tem_s][j] + sum[start][j];
                    s[start][j] = tem_s;
                    max[start][j] = tem_max;
    // printf("MAX%d    ",tem_max);   //cky
                }
            }
        }
    }
    
    tem_start = 0;
    tem_max = max[0][number-1];
    for (start=1; start<number; start++)
    {
        if (max[start][start-1] > tem_max)   //取最大值
        {
            tem_start = start;
            tem_max = max[start][start-1];
        }
    }
 //cout<<"M"<<tem_max<<endl;  //cky
    start = tem_start;
    printf("最大值:%d\n",tem_max);

    get_step(start,MOD(start-1));
    for (j=0; j<number; j++)
    {
        tem_i[j] = j;
    }

    print(step[0]);
    for (k=0; k<number-2; k++)
    {
        istep = MOD(step[k]+1);
        start = tem_i[istep];
        int itemp = tem_i[step[k>;
        while ((tem_i[istep] == start) && (istep != step[k]))
        {
            tem_i[istep] = itemp;
            istep = MOD(istep+1);
        }
        print(step[k+1]);
    }
    printf("%d\n",sum[0][number-1]);
 printf("\n");

}