NYOJ 536マトリックスチェーンにクラシックdpを乗じる

月試合の時の問題で、経典のdpです.
遷移方程式は、m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];m[i][j]は、iからjまでの乗算の最小回数を表す.p[i−1],p[i]はそれぞれi番目の行列の行と列である.タイトル:
楽しいmdd
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
3
説明
himddはある日暇で退屈で、手当たり次第に本を持って、手当たり次第にページをめくって、不思議な問題を説明して、行列に関係するもののようです.
3つの行列とその行列A 1(10*100),A 2(100*5),A 3(5*50)を与えた.himddは計算行列に必要な乗算回数を算出しようとしたが,計算順序が異なり,必要な乗算回数も異なることが分かった.
次のようになります.
(A1*A2)*A3 : 10*100*5+5*10*50=7500;
A1*(A2*A3) : 5*100*50+10*100*50 =75000;
彼は行列を計算するのに必要な最小乗算回数を知りたいと思っています.すぐに1つの解法が誕生しました.少しhappy~~今、彼はあなたにも1つの解法を見つけることができますか?
注意:行列は順序を変更できません.
入力
複数のテストデータ(<=100)があり、各グループは以下のように記述されている.
1行目は、整数n行列の個数(1<=n<=100)がある
次はn行
i行目には2つの整数があり、r,cはi番目の行列の行列を表す.(1<=r,c<=100)
しゅつりょく
計算マトリクスに必要な最小乗算回数を出力します.
サンプル入力

3
10 100
100 5
5 50

サンプル出力

7500

acコード:

#include <iostream>
#include <cstdio>
using namespace std;
const int N=210;
int p[N];
int d[105][105];
#define MAX 100000000;
int main(){
	int n;
	while(~scanf("%d",&n)){
	  for(int i=1;i<=n;++i)
		  scanf("%d%d",&p[i-1],&p[i]);
	  for(int i=1;i<=n;++i)
		  d[i][i]=0;
	  for(int l=2;l<=n;l++){
		  for(int i=1;i<=n-l+1;i++){
		    int j=i+l-1;
			d[i][j]=MAX;
			for(int k=i;k<=j-1;k++){
			  int v=d[i][k]+d[k+1][j]+p[i-1]*p[k]*p[j];
			  if(v<d[i][j])
				  d[i][j]=v;
			}
		  }
	  }
	  printf("%d
",d[1][n]);
	}
	return 0;
}