SRM523 Div1 500

問題

1*1*1〜1*1*kのレゴブロックが無数にある。
土台が1*1*wのところに重ねていき、高さをhにしたい(土台は高さに含めない)。
条件として、ブロックを重ねるとき、重ねるブロックからはみ出ないようにする必要がある。
そのような重ね方の組み合わせは全部で何通りあるか？MOD1000000007で答える。

考え方

見るからにDP。

使えそうな式として、
　dp[残りの高さi][土台の幅j] := 積み上げ方の数
があれば、dp[i][j]はdp[i-1][?]から求められそう。

単純に、土台の幅をどうブロックを組み合わせて置くかを試すのは、組み合わせが多すぎて×。

ここでDPで、i-1までdpが計算されているとして、幅xのブロックを置いたあと、1空マス、残り、という風にして、
[ x ][ ][ 残り ]
xの部分は、幅xのブロックの組み合わせ*dp[i-1][x]になる。
残りの部分は、dp[i][残り]になる。

この残りの部分は計算できて、jの部分を0,1,...,wと順番に計算すると考えると、
[ x ][ ][ 残り ]全体の長さがjのとき、残りの部分はdp[i][j-x-1]で、j-x-1はjより小さく、すでに計算済みである。

結局、dp[i][j]は、上のようなパターンで計算できるので、
　dp[i][j] = {幅xのブロックの組み合わせ * dp[i-1][x] *dp[i][j-x-1]}の合計値 + 幅wのブロックの組み合わせ * dp[i-1][w]
の計算になる。

(全部に置かないパターンは、xが0の時に内包されている)
計算の都合上、dp[0][]はすべて1(通り)。

次に、「幅xのブロックの組み合わせ」を考える。
使えるブロックの幅は最大でもkまでであることに注意する。(k=wなら2^{x-1}になる？)

これも同じようなDPで、
[ 0〜kまでのブロック ][ 残り ]
と考えることができて、
　dp[i] := {幅xのブロックを置く * dp[i-x]}の合計値
になる。「幅xのブロックを置く」は1通りしかないので、結局、
　dp[i] := dp[i-x]の合計値(xは1からkまで)
で求まる。

これを前計算しておいて、上の計算をすれば、dp[h][w]が答えになる。

反省

• 典型的なDPっぽい
  • 前部分xを押さえて、残りは計算済み、みたいな？
• 複数回(再帰的)のDP適用を考える