SRM 709 DIV1 Medium: Softmatch

http://codeforces.com/blog/entry/49911?#comment-344869

↑の理解

|patterns|<=5なのでこれの最大ケース|patterns|=5の場合だけ考えてみよう。以下のような愚直なDPはすぐに思いつく。

dp[i][p[0]][p[1]][p[2]][p[3]][p[4]]

:= Sのi番目まで確定していて、pattenrs[j]についてはp[j]文字まで一致している。このときの単語の出現個数の最大値。

しかし、これでは間に合わないから、DPテーブルの次元を減らしたい。

p[0]>=p[1]の場合を考えてみよう。ただし、p[1]の値は具体的にはわかっていないとする。

p[0]の値によって、Sの確定部分のうち直前p[0]文字は求まる。このSの直前p[0]文字、S[i-p[0],i)によって、p[1]の値を具体的に求めることができる。つまり、pattenrs[1]のprefixとS[i-p[0],i)のsuffixが最大何文字一致しているかがわかる。同様に

p[0]>=p[j], (j!=0)ならば p[j]の値をすべて求めることができる。

p[0]が最大とは限らないが、あるp[x]が最大でありその値がわかっているならば他のp[j](j!=x)は求めることができる。よって、先のDPは以下のように変換できる。

dp[i][j][k]

:= Sのi番目まで確定していて、patterns[j]が一致文字数が最も多く、その文字数はkである。このときの単語の出現個数の最大値。

これを解けば良い。

思いつき方?

とりあえず愚直なDPを考えてみる。そのDPの次元のとり方に無駄がありそうなら、次元を減らそうと試みる。p[i]は何に畳み込めるか。逆に考えるとわかりやすい?p[i]をすべて求めるのに必要最小限の情報は何か。