AOJ 1611 ダルマ落とし

Daruma Otoshi | Aizu Online Judge

dp[l][r] = {lからrまでの区間の状態}と持ってDPする、区間DPの問題。
この問題ではdp[l][r] = {lからrまでの区間で叩ける最大のブロック数}とする。
dp[l+1][r-1]の区間が全てのブロックを叩き出すことができ、l番目とr番目のブロックの重さの差が1以下のときdp[l][r] = r-l+1 となる。また、k番目(l <= k < r)のブロックで区切り、dp[l][k] + dp[k+1][r] の最大がdp[l][r]となる。
全ての取りうる区間の幅のブロックを小さい方から試すのがO(n^2)、その区間の中の区切るブロックを全て試すのがO(n)でO(n^3)で計算できる。