Single Blokus

このゲームのルールを考えると以下のことが言えます．

$a_1,a_2, \cdots a_k$の$k$個のブロックを選んで適切に向きを変える． $a_j$個目の幅を$x'_{a_j}$,高さを$y'_{a_j}$とする． ここで，このゲームに勝利することと以下の2つの式が成立することは同値である．

• $x'_{a_1}+x'_{a_2}+ \cdots + x'_{a_k}=H$
• $y'_{a_1}+y'_{a_2}+ \cdots + y'_{a_k}=W$

これは$2$変数の部分和問題に帰着することができるので．動的計画法を用いて条件を満たす選び方が存在するかどうかを確かめればよいです．

計算量は時間空間ともに$O(NHW)$です．