距阵连乘.cpp

里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等

#include <iostream>
#include <iomanip>
using namespace std;
#define N  20
int save[N][N] ;
int Next[N][N] ;
void Print(int i ,int j )
{
	if (i < j)
    {
		int k = Next[i][j];
        if (i < k)
            cout << "(";
            Print(i, k);
        if (i < k)
            cout << ")";
        if (k + 1 < j)
           cout << "(";
           Print(k + 1, j);
        if (k + 1 < j)
           cout << ")";
    }
    else if (i == j)
        cout << "A" << i;
    
}


int  MatrixMutip(int number[] ,int i,int j)
{
	if(i < j && save[i][j] == 0 )
	{
	   save[i][j] = 999999 ;
	   int temp ;
	   for(int k = i ;  k < j ;  k ++)
	   {
		   temp = MatrixMutip(number,i,k) + MatrixMutip(number,k+1,j) + number[i]*number[k]*number[j];
		   if(save[i][j] > temp)
		   {
			   save[i][j] = temp ;
			   Next[i][j] = k;
		   }
	   }
	}
	return save[i][j] ;
}

int main()
{
	int n,i,j,number[N];
	freopen("in.txt","r",stdin) ;
	cin>>n ;
	for(i = 0  ; i < n ; i ++)
	   cin>>number[i] ;
	for (i = 0 ; i < n ; i ++)
		for( j = 0  ;  j < n ; j ++)
		save[i][j] = 0 ;
    MatrixMutip(number ,0,n-1) ;
	for(i = 0  ; i < n ; i ++)
	{
		for(j = 0  ; j < n ; j ++)
			cout<<save[i][j]<<"    " ;
		cout<<endl;
	} 
	for(i = 0  ; i < n ; i ++)
	{
		for(j = 0   ; j < n ; j ++)
			cout<<Next[i][j]<<" " ;
		cout<<endl;
	}
	Print(0,n-1) ; cout<<endl;
	return 1;
}