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]をすべて求めるのに必要最小限の情報は何か。