问题：
给出两个字符串 s,t ，和一个整数 k ，进行如下操作 :
由 1 至 length(s) 依次从 s 中选出 k 个不相交的连续的非空子串 p1,...,pk .
由 1 至 length(t) 依次从 t 中选出 k 个不相交的连续的非空子串 q1,...,qk .
保持 p1,...,pk 在 s 中的相对位置顺序，保持 q1,...,qk 在 t 中的相对位置顺序。
使得 p1 = q1,p2 = q2,...,pk = qk ，且最大化选出的 k 个子串的长度之和。
其中字符串从 1 开始标号，length(s) 表示字符串 s 的长度。
为防止乱搞骗分，故此题采用捆绑测试。
subtask1 20pts : n, m ≤ 10, k ≤ 2 .
subtask2 25pts : n, m ≤ 100, k ≤ 3 .
subtask3 25pts : n, m ≤ 1000, k = 1 .
subtask4 30pts : n, m ≤ 1000, k ≤ 10
解：
看到这数据范围我就想到了骗分
令$f[i][j][k] (表示前i个前j个匹配k个的最大代价
)f[i][j][k]=max(f[tmp1-][tmp2-1][k-1]+len)$
所以我们要进行枚举但是要超时 但是还是有55分
subtask3 25pts : n, m ≤ 1000, k = 1 .
我突然想到了区间HASH
我又混了25pts
好吧说正解
令$f[i][j][k] (表示前i个前j个匹配**最少k个**的最大代价
记录ij为结尾最远能延伸到的长度
)f[i][j][k]=max(f[i-1][j-1][k],f[i-1][j][k],f[i][j-1][k])(
)f[i][j][k]=max(f[i-len][j-len][k-1]+len);$
为甚么这样可以呢？
其实此题无非就是 相同的可以分成多段
那其实可以等价于 一个串相同的可以分成多段
好吧思路清奇 我想不到....