ex_1.cpp

问题描述 给定n个矩阵A1

#include <iostream>
using namespace std;

void Traceback(int i,int j,int **s);

int N;

int main()
{
	int num=0;
	int **m;
    	int **s;
    	int *p;
	int i;
	while(cin>>N)
	{
		++num;
		m = new int *[N+1];
		s = new int *[N+1];
		for(i=1; i<=N ; i++)
		{
			m[i] = new int [N+1];
			s[i] = new int [N+1];
		}
		p = new int[N+1];
		for(i=0;i<=N;i++)
			cin>>p[i];
		for(i=1;i<=N;i++)
			m[i][i]=0;
		//m[i][i]=0

		if(N==1)
		{
			cout<<"Case "<<num<<endl;
			cout<<"0"<<' '<<"A1"<<endl;
		}
		else if(N==2)
		{
			cout<<"Case "<<num<<endl;
			cout<<(p[0]*p[1]*p[2])<<' '<<"A1A2"<<endl;
		}

		else
		{
			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]+p[i-1]*p[i]*p[j];
					s[i][j]=i;
					for(int k=i+1;k<j;k++)
					{
						int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
						if(t<m[i][j])
						{
							m[i][j]=t;
							s[i][j]=k;
						}
					}
				}
			cout<<"Case "<<num<<endl;
			cout<<m[1][N]<<' ';
			Traceback(1,N,s);
			cout<<endl;
		}
	}
	return 0;
}

void Traceback(int i,int j,int **s)
{
	if(i==j)
	{
		cout<<"A"<<i;
	}
	else if(i+1==j)
	{
		cout<<"(A"<<i<<"A"<<j<<")";
	}
	else
	{
		if(i==1&&j==N)
		{
			Traceback(i,s[i][j],s);
			Traceback(s[i][j]+1,j,s);
		}
		else
		{
			cout<<"(";
			Traceback(i,s[i][j],s);
			Traceback(s[i][j]+1,j,s);
			cout<<")";
		}
	}
}