林一婧-5.5.txt

这是很不错的计算机算法

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

#include <stdlib.h>
#include <stdio.h>
#define max(a,b)   ((a>b)?a:b)

void merge(int * p,int n,int * * m);

int main()
{    
	int n=0; 
	int * * m;
	ifstream in("input.txt");
	ofstream out("output.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	in>>n;
	int * p=new int[n+1]; 
	m=new int*[n];
	for (int i=1; i<=n; i++)
      m[i]=new int[n];
      
  bool err=false;
	for ( i=0;i<=n && !err && in.good() ;i++)
	{
		in>>p[i];
		if (p[i]<=0){
			out<<"error";
			err=true;
	  }
	}
	if (!err){
		merge(p,n,m);
		out<<m[1][n];
	}
		
	out<<flush;
	out.close();
	in.close();
	return 1;
}
void merge(int * p,int n,int  * * m)
{	
	for ( int i=1;i<=n;i++)
     m[i][i]=0;
  for (int r=2;r<=n;r++)
     for ( i=1;i<=n-r+1;i++)
		 { 
		 	int j=i+r-1;
      m[i][j]=m[i+1][j]+(3*max(max(p[i-1],p[i]),p[j])-p[i-1]-p[i]-p[j]);
	   	for(int k=i+1;k<j;k++)
	   	{ 
	   		int t=m[i][k]+m[k+1][j]+3*max(max(p[i-1],p[k]),p[j])-p[i-1]-p[k]-p[j];
	      if (t>m[i][j])
		    m[i][j]=t;   
      }
	 	 } 
}