#include <iostream>
using namespace std;
#define INF 2000000000
#define N  5
int p[N];
int res[N][N];
int path[N][N];


void Print_MCM(int i,int j)
{
  if (i==j) 
  {
	  printf("A%d",i);
  }
  else
  {
	  printf ("(");
	  Print_MCM(1,path[i][j]);
	  printf(" * ");
	  Print_MCM(path[i][j]+1,j);
	  printf(")");
  }
}
int main()
{
	int n,i,j,l,k;
	while (cin>>n && n)
	{
		for (i=0;i<n;i++)
		{
			cin>>j>>k;
			p[i] = j;
		}
		p[n] = k;
		//for (i=1;i<=n+1;i++) cout<<p[i]<<endl;
		for (i=1;i<=n;i++) res[i][i]=0;
		for (l=2;l<=n;l++)
		{
			for (i=1;i<n-l+1;i++)
			{
				j = i+l-1;
				res[i][j] = INF;
				for (k=i;k<=j-1;k++)
				{
					int q = res[i][k] + res[k+1][j] + p[i-1]*p[k]*p[j]; 
					if ( q < res[i][j])
					{
						res[i][j] = q;
						path[i][j] = k;
					}
				}
			}
		}
		Print_MCM(1,n);
		printf("\n");
	}
}
INPUT ：
3
1 5
5 20
20 1
OUTPUT
(A1 x (A2 x A3))
为什么我输出((A1 x A2) x A3)
想不出来那里错

• Re:经典矩阵连乘问题,不知为什么答案错，帮忙看看 (460) dinglinbin 2007-10-19 09:21:19