南郵OJ 1038最小代価ツリー

最小コストツリー
時間制限(通常/Java):
1000 MS/3000 MS実行メモリ制限:65536 KByte総提出:388テスト合格:98
試合の説明
以下の方法を最小代価のアルファベットツリーと呼ぶ:正の整数シーケンス、例えば、4,1,2,3を与え、数の位置を変更しない条件で加算し、加算ごとに得られる和を括弧でマークする.たとえば、((4+1)+(2+3)=((5)+(5)))=10です.原数が4,1,2,3でないことを除いて、残りはすべて中間結果であり、例えば5,5,10であり、中間結果を加算して:5+5+10=20を得ると、数20はこの数列の1つの代価と呼ばれ、別のアルゴリズムが得られると:(4+((1+2)+3)=(4+((3)+3))=(4+(6)))=10、数列のもう1つの代価は:3+6+10+19である.N個の数を与えると、N−1対の括弧を加えて、この数列の最小代価を求めることができる.注意:結果範囲はlongintを超えません.
入力
第1の挙動数N(1≦N≦200)、第2の挙動N個の正の整数、整数間をスペースで区切る.
しゅつりょく
出力は1行のみです.つまり、最小世代の価値です.
サンプル入力
4 4  1  2  3
サンプル出力
19
テーマソース
OIBHシミュレーション試合

#include <stdio.h>
#define MAX_N 200
#define LARGE 100000000
#define MIN(a,b) (a<b?a:b)
int main(void){
	unsigned short N=0,i=0,j=0,k=0,l=0;
	unsigned long g[MAX_N][MAX_N]={0};
	unsigned long f[MAX_N][MAX_N]={0};	
	scanf("%hu",&N);
	for(i=0;i<N;++i)
		scanf("%ld",&g[i][i]);
	for(i=0;i<N;++i)
		for(j=i+1;j<N;++j)
			g[i][j] = g[i][j-1]+g[j][j];
	for(i=0;i<N;++i)
		f[i][i] = 0;	
	for(l=1;l<N;++l){
		for(i=0;i<N-l;++i){
			j = i+l;
			f[i][j] = LARGE;
			for(k=i;k<=j-1;++k){
				f[i][j] = MIN(f[i][j],f[i][k]+f[k+1][j]);
			}
			f[i][j] += g[i][j]; 
		}
	}
	printf("%ld
",f[0][N-1]);
	return 0;
}