最小コストツリー

タイトル:以下の方法を最小代価と呼ぶアルファベットツリーを説明します:正の整数シーケンスを与えて、例えば: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 4 1 2 3サンプル出力19
分析:この問題は石の合併問題に似ている:直線の上にN山の石が並べられていて、今石を秩序正しく1山に合併しなければならない.毎回隣接する2山の石を移動して合併するしかなく、合併にかかる石の数を規定している.このN山の石を1山にまとめる総費用を最小(または最大)にするアルゴリズムを設計した.行列連乗を熟知すれば,このような問題をよく知っているに違いない.マトリクス連乗も毎回隣接する2つのマトリクスをマージします(計算方法が異なるだけです).では,石子結合問題は行列連乗法で解決できる.では、最適なサブ構造は何でしょうか.Nスタックがある場合、1回目の操作は必ずn-1対の中から1対を選択してマージし、2回目はn-2対の中から1対を選択してマージする.これに類する.f[i][j]はi-jマージの最適値を表し、sum[i][j]はiスタック石からjスタック石までの合計数を表し、繰返し式は以下の通りである.
(行列連乗は『アルゴリズム導論』が見られ、詳しく述べている)
 
コードは次のとおりです.

#include <stdio.h>
#include <limits.h>

int N,arr[210],sum[210][210],m[210][210];

void calSum();
void calMinSum();

int main()
{
	int i;

	scanf("%d",&N);  //      
	for (i=0;i<N;i++)
	{ 
		scanf("%d",&arr[i]);  //     
	}

	calMinSum();  //       

	return 0;
}

void calSum()
{
	int i,j,k;

	for (i=0;i<N;i++)  //   i j    
	{
		for (j=i;j<N;j++)
		{
			for (k=i;k<=j;k++)
			{
				sum[i][j]+=arr[k];
			}
		}
	}
}

void calMinSum()
{
	int r,i,j,k,iTemp;  //r   

	calSum();

	for (i=0;i<N;i++)
	{
		m[i][i]=0;
	}

	for (r=2;r<=N;r++)
	{
		for (i=0;i<N-r+1;i++)
		{
			j=i+r-1;

			m[i][j]=INT_MAX;
			for (k=i;k<=j-1;k++)
			{
				iTemp=m[i][k]+m[k+1][j]+sum[i][j];

				if (iTemp<m[i][j])
				{
					m[i][j]=iTemp;
				}
			}
		}
	}

	printf("%d
",m[0][N-1]);

}