shizi .cpp

算分分析课程中的石子合并问题实现

#include<iostream.h>
void main()
{
int a[101],b[101],c[101],d[101];
int m[101][101],i,j,k,t,n,min,max;
cin>>n;
t=n;
for(i=0;i<n;i++)
{
  cin>>a[i];
  b[i]=a[i];
}
for(i=0;i<n;n--)              //求最小得分方法
{
  if(n==1)
  {
   cout<<a[0]<<" "<<endl;
   break;
  }
  for(j=0;j<n;j++)
  {
   if(n==2)
   {
    m[0][1]=a[0]+a[1];
    break;
   }
   else
    m[j][(j+1)%n]=a[j]+a[(j+1)%n];
  }
  min=m[0][1];
  for(j=0;j<n;j++)
  {
   if(n!=2)
   {
    if(min>m[j][(j+1)%n])
     min=m[j][(j+1)%n];
   }
   else
    break;
  }
  for(j=0;j<n;j++)
  {
   if(n==2)
   {
    a[0]=-1*a[0];
    a[1]=-1*a[1];
    break;
   }
   else
    if(min==m[j][(j+1)%n])
    {
     a[j]=-1*a[j];
     a[(j+1)%n]=-1*a[(j+1)%n];  
    }
  }
  for(k=0;k<n;k++)          //输出一次合并的结果
  {
   cout<<a[k]<<" ";
  }
  a[(j++)%n]=min;
  for(j=0,k=0;k<n;k++)
  {
   if(a[k]>0)
   {
    c[j]=a[k];
    j++;
   }
  }
  for(k=0;k<j;k++)
   a[k]=c[k];
  cout<<endl;
}
for(i=0;i<t;t--)                 //求最大得分方法
{
  if(t==1)
  {
   cout<<b[0]<<" "<<endl;
   break;
  }
  for(j=0;j<t;j++)
  {
   if(t==2)
   {
    m[0][1]=b[0]+b[1];
    break;
   }
   else
    m[j][(j+1)%t]=b[j]+b[(j+1)%t];
  }
  max=m[0][1];
  for(j=0;j<t;j++)
  {
   if(t!=2)
   {
    if(max<m[j][(j+1)%t])
     max=m[j][(j+1)%t];
   }
   else
    break;
  }
  for(j=0;j<t;j++)
  {
   if(t==2)
   {
    b[0]=-1*b[0];
    b[1]=-1*b[1];
    break;
   }
   else
    if(max==m[j][(j+1)%t])
    {
     b[j]=-1*b[j];
     b[(j+1)%t]=-1*b[(j+1)%t];
     break;
    }
  }
  for(k=0;k<t;k++)
  {
   cout<<b[k]<<" ";
  }
  b[(j++)%t]=max;
  for(j=0,k=0;k<t;k++)
  {
   if(b[k]>0)
   {
    d[j]=b[k];
    j++;
   }
  }
  for(k=0;k<j;k++)
   b[k]=d[k];
  cout<<endl;
}
}