ADLSI : 連鎖行列積

参考:アルゴリズムイントロダクション15章 動的計画法
コード中のコメントはここに書いてあることです…。
勘違いしてるかもしれません…

ソースコード

/*
	連鎖行列積問題
	
	演算結果はカッコ付けの順序にはよらないが、カッコ付けの順番には依存する
		ー>乗算回数を最小にするカッコ付けを決定する
		 
	P(n) : n個の行列に対するカッコ付けの個数

	P(n) = 1 (n = 1)
	P(n) = \sum_{k = 1}^{n - 1} P(k) * P(n - k) (n >= 2)

	Ω(4^n/n^{3/2}) 

	問題の最適解に部分問題の最適解が含まれる
		ー>部分問題最適性

	m[i][j] = A_i, A_jの計算に必要なスカラ乗算の最小回数 (A_n : 行列)

	最適解はA_kとA_k+1で分割すると仮定する

	m[i][j] = 0 (i = j)
	m[i][j] = m[i][k] + m[k + 1][j] + p[i].first * p[k].second * p[j].second(i ≠ j)
*/

const int INF = 1 << 29;

int main()
{
	int n;
	scanf("%d", &n);

	int left[100], right[100];
	int m[100][100];

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			m[i][j] = INF;

	for(int i = 0; i < n; i++)
	{
		scanf("%d%d", left + i, right + i);
		m[i][i] = 0;
	}

	for(int l = 1; l < n; l++)
	{
		for(int i = 0; i < n - l; i++)
		{
			int j = i + l;
			for(int k = i; k < j; k++)
			{
				m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + left[i] * right[k] * right[j]);
			}
		}
	}

	printf("%d\n", m[0][n - 1]);	
}

余談

VisualStudio2012で効率の良い標準入力の仕方教えてください。(コマンドライン引数使ってもいいとは思うけどよくわかっていない…)