Codeforces #396 Div.2 C: Mahmoud and a Message
解法
まず、[l,r)の部分文字列を作れるかどうか判定するのに
各文字のカウント部分和を計算しておき、
文字iについては
cnt[i][r] - cnt[i][l]
で数えられる。つまり[l,r)の範囲に文字iがあるかどうかわかる。
[l,r)の範囲にあるすべての文字iについて
r-l >= a[i]
が成り立つかチェックする。これで[l,r)の範囲の部分文字列の判定はできた。
あとはこれを使って2種類のDPを解く。
f[x文字目まで見た][直前j個は連続] = 場合の数
g[i文字目まで見た][直前j個は連続] = 部分文字列の数の最小値
文字列全体について、分割の仕方の数と部分文字列の数の最小値は求まった。
最長の部分文字列はDPの更新時についでに計算できる。