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の更新時についでに計算できる。