【ダイナミックプランニング】マトリクス連乗問題

Description

 
 
 
 
n個の行列{A 1,A 2,...,An}が与えられ,AiとAi+1は乗算可能であり,i=1,2,...,n−1である.このn個の行列の連乗積A 1 A 2…Anを算出する.行列乗算は結合則を満たすため、計算行列の連積には多くの異なる計算順序があることができる.この計算順序は括弧で決定することができる.1つのマトリクス連積の計算順序が完全に決定され、すなわち、その連積が完全に括弧を付けた場合、この順序で2つのマトリクス相乗の標準アルゴリズムを繰り返し呼び出してマトリクス連積を計算することができる.完全カッコ付けマトリクスの連続積は、(1)単一マトリクスが完全カッコ付けマトリクスである;(2)行列連乗積Aが完全にかっこ付けされている場合、Aは完全にかっこ付けされた2つの行列連乗積BとCの積として表され、かっこ付けされているA=(BC)である.与えられた連続n個の行列{A 1,A 2,...,An}(行列Aiの次元数がpi−1である×pi,i＝1,2,…,n)は、計算行列連乗A 1 A 2…Anの計算順序(完全括弧付け方式)をどのように決定し、この順序で計算行列連乗を計算するのに必要な数乗回数を最小限に抑えるかを決定する.
 
 
 
 

Input

 
 
 
 

 1  n ，  n   
    n ，      ，    Ai(1≤i≤n)     
      An     

 
 
 
 

Output

 
 
 
 

       A1A2…An       

 
 
 
 

Sample Input

 
 
 
 

6
30
35
15
5
10
20
25

 
 
 
 

Sample Output

 
 
 
 

15125

#include  
using namespace std;
#define N 100
int p[N];
int m[N][N];
  
int main()  
{  
	int n,i,j,k,min,cut;
	while(cin>>n)
	{
		for(i=1;i<=n+1;i++)
			cin>>p[i];
		for(i=1;i<=n;i++)
				m[i][i]=0;//      
		for(j=2;j<=n;j++)//        ，           
		{
			for(i=1,k=j;i