Typical DP Contest I - イウィ - ツバサの備忘録

解法

操作をいろいろ試してみると、一連の操作で消すことができる部分というのは区間になっていることがわかります。

$dp[l][r] = [l,r)$ の区間の文字全てを消すことができるかどうか

という区間DPを考えます。 $r-l$ が3の倍数でない時はもちろんNOです。
$[l,r)$ を全て消去するには、

$l \leq m \leq r$ を満たす $m$ について、 $dp[l][m],dp[m][r]$ が共にYESとなるものが存在する
$S_{l},S_{r-1}$ がi、 $S_{m}$ がwであり、 $dp[l + 1][m]$ と $dp[m+1][r-1]$ がYES

のいずれかを満たしていればよいです。( $dp[l][l\$ のような空の区間についてもYESとみなしています)
よって、上記のいずれかを満たしていればYESとすることで、ある区間について全て削除できるかどうかがわかるようになります。
さて、

$sum[l][r] = [l,r)$ について行うことができる操作の最大回数

として、再び区間DPをすることでこの問題に答えていきます。
$dp[l][r]$ がYESのとき、 $sum[l][r]$ は明らかに $(r-l)/3$ となります。
そうでない場合は、
$sum[l][r] = max(sum[l][m] + sum[m][r])$
によって計算できます。
以上により、答えを求めることができました。

感想

~~昔はとっかかりすらつかめなかったものがさらりと解けると嬉しいですね！考察、実装ともにサクサク行けたので良かったです。~~　

嘘解法はよくないですね！！！(上の解説は修正済みです)