[AOJ] No. 0363 積み荷の配置

問題

方針

\( i \) 列目に荷物が置けるかどうかは \( i – 1 \) 列目と \( i \) 列目を調べれば良いので、動的計画法を行います。各列の状態は荷物か置けるマスがあるかどうかの \( 2 \) 通りであり \( 4 \)マスあるので、全体で \( 16 \) 通りあります。なので、bitDP を行います。

更新式

\( d(i, j) \) を \( i \) 列目のマスが \( j \) であるときの置くことができる荷物の最大数とします。ここで、\( j \) は \( 2 \) 進数で表現されたマスの状態とします。\( i \) 列目のマスの状態を \( b_i\) とすると、初期値は \( d(0, b_0) = 0\) とし、それ以外は、\( d(i, j) = -1 \) とします。

荷物の置き方は、\( 1100, 0110, 0011, 1111\) の \( 4 \) 通りあり、荷物を置かないパターンは \( 0000 \) と表します。

\( d(i – 1, j) \neq -1\) のとき、遷移できる状態を考えます。ここで、\( c_1 = 1100 \) とします。  \( i -1, \ i\) 列目に、\( c_1 \) の置き方ができるとき、\( j \wedge c_1 = 0 \) ならば、\( d(i, b_i \vee c_1) \leftarrow d(i -1, j) + 1 \) と更新することができます。

コード