fc2ブログ



カード

2009.07.14 19:26  パソコン甲子園 2006

パソコン甲子園 2006 カード


連鎖行列積問題の解法と同様に動的計画法で解きます。

例えば、下図のように5枚のカードの山があるとします。

パソコン甲子園 2006 カード


まず最初に、隣り合う2組の山を重ねるときの最小のコストを計算します(j = 1)。
i を 重ねる山の左端の山とすると、i = 1, 2, 3, 4 について計算します。

つぎに、隣り合う3組の山を重ねるときの最小のコストを計算します(j = 2)。
i = 1, 2, 3 について計算します。

つぎに、隣り合う4組の山を重ねるときの最小のコストを計算します(j = 3)。
i = 1, 2 について計算します。

同様に、隣り合うN組の山を重ねるときの最小のコストを計算します(j = N-1)。
i = 1 について計算します。


各 j の値での最小コストの計算方法を考えます。
例えば、j = 3, i = 1 の場合の最小コストは以下の中で最小のものとなります:

  • カードの山[1]とカードの山[2,3,4]をそれぞれ重ねるのに要した最小コスト + それら2つの山を重ねるコスト (k = i+1)
  • カードの山[1,2]とカードの山[3,4]をそれぞれ重ねるのに要した最小コスト + それら2つの山を重ねるコスト (k = i+2)
  • カードの山[1,2,3]とカードの山[4]をそれぞれ重ねるのに要した最小コスト + それら2つの山を重ねるコスト (k = i+3 = i+j)

スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ