AOJ 1611 - ダルマ落とし - ツバサの備忘録

解法

区間DPをします。
$dp[i][j] =$ 区間 $[i,j]$ の中で落とせるブロックの最大値
とすると、答えは $dp[1][n]$ となります。
まず、 $dp[i][i] = 0$ となります。続いて、 $|w_{i} - w_{i+1}| \leqq 1$ ならば $dp[i][i+1] = 2$ となります。
では、 $dp[i][j]$ を求めていきます。
まず、 $dp[i+1][j-1] = j - i - 1$ (すなわち、区間 $[i+1,j-1]$ のブロックをすべて落とせるということです)かつ、 $|w_{i} - w_{j}| \leqq 1$ ならば、区間 $[i,j]$ のブロックを全て落とせるということになるので、答えは $j-i+1$ となります。
それ以外の場合、 $[i,j]$ を適当な2つの区間 $[i,k],[k+1,j]$ に分割し、それぞれで落とせるブロックの最大値の和を求め、 $k$ について全探索しながら最大値を求めればいいです。
$dp[i][j] = max(dp[i][k]+dp[k+1][j])$
ということです。
あとはこのDPを行えば、答えを求めることができます。

感想

$i$ 番目のブロックと $j$ 番目のブロックをペアで落とすには、 $[i+1,j-1]$ の区間のブロックを全て落とす必要がある、ということに気づき、そこからうまく調べる方法が無いか、を探しました。端の2つのブロックを落とさない場合は、適当に2つの区間に分割すれば最適解を求められるだろう、ということで上のようなDPをしました。