Codeforces Round #625 (Div. 2, based on Technocup 2020 Final Round)- C. Remove Adjacent

問題リンク 周りの人間が誰一人として区間DPでやってなくて泣いたので


dp[i][j] := [i,j)で消せる文字の最大数

としましょう。そうすると


dp[i][j] \leftarrow \mathrm{max}(dp[i][k] + dp[k][j])

はいいでしょう。

あとは消す場合を考えるといいですが、文字bが消える場合を考えると


a[全部消える]b[文字列] \\
[文字列]b[全部消える]a

のどちらかなので


dp[i][j] \leftarrow dp[i][k] + dp[k + 1][j] + 1 \qquad (s[k] - s[i-1] == 1 かつ\  dp[i][k] == k - i) \\
dp[i][j] \leftarrow dp[i][k] + dp[k + 1][j] + 1 \qquad (s[k] - s[j] == 1 かつ\ dp[k][j] == j - k)

となる。あとはこれを遷移させることで求めることができました。

提出コード

codeforces.com