カード
2009.07.14 19:26 パソコン甲子園 2006
パソコン甲子園 2006 カード
連鎖行列積問題の解法と同様に動的計画法で解きます。
例えば、下図のように5枚のカードの山があるとします。
まず最初に、隣り合う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 の場合の最小コストは以下の中で最小のものとなります:
連鎖行列積問題の解法と同様に動的計画法で解きます。
例えば、下図のように5枚のカードの山があるとします。

まず最初に、隣り合う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) | ↑ページトップ |