TDPD I イウィ

tdpc.contest.atcoder.jp

区間DPの問題。AOJ 1161ダルマ落としと似てる。

dp[l][r] = {lからrまでの区間で操作をできる回数}としてDPする。
区間lからrで間の区間(l+1からr-2orl+2からr-1)が全て削除でき、削除したあとに残る文字列がiwiならばその区間は全て削除できる。
また、区間内でk番目(l <= k < r)で区切り、dp[l][k] + dp[k+1][r] の最大がdp[l][r]となる。
幅が小さい区間から試していくことでO(|S|^3)で計算できる。