2.cpp

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

#include<iostream>
using namespace std;
int i,s;
int t(int a,int b,int *q);
void Mat(int p[],int n,int m[][200],int flag)  

{ 

    for(int i=0;i<n;i++) 

       m[i][0]=m[i][1]=m[0][i]=0; 

    for(int r=2;r<n;r++) 

     for(int i=1;i<n;i++) 

	 {   

         int j=(i+1)%n;

		 if((i+1)>=n) j++;

         int temp=t(i,r,p); 

         m[i][r]=m[j][r-1]+temp;

       for(int k=2;k<r;k++) 

	   { 

          int x=(i+k)%n;

		  if((i+k)>=n) x++;

          int t=m[i][k]+m[x][r-k]+temp; 

          if(!flag)

			 if(t<m[i][r]) 

             m[i][r]=t; 

          if(flag && t>m[i][r]) 

                  m[i][r]=t;

	   }

	 }

}

int t(int a,int b,int* q)

{ 
	int sum=0;
    for(int i=a;i<b+a;i++)
	{
       int j=i%s;
       if(i>=s) j++;
       sum+=q[j]; 
	}
    return sum;
}

int result(int m[][200],int n,int flag)
{   int min=10000,max=0,i;

    if(!flag)

	{
           for(i=1;i<n;i++)
            if(min>m[i][n-1])
             min=m[i][n-1];
			return min;

	}

	else {

	   for(i=1;i<n;i++)
    	if(max<m[i][n-1])
    	max=m[i][n-1];
        return max;
	}
}

int  main()

{

	int m[200][200];
	int p[200];
    cin>>s;
	s++;
	p[0]=0;
    for(i=1;i<s;i++)
	{
		cin>>p[i];
	}
	if(s==2)
	{
		cout<<"0"<<endl;
		cout<<"0"<<endl;
	}
	else
		{
	      int n;
	      n=s;
   	      Mat(p,n,m,0);
          int min=result(m,n,0);
          Mat(p,n,m,1);
          int max=result(m,n,1);
           cout<<min<<endl;
	       cout<<max<<endl;
		}
	
	return 0;

}