D

求最多被分成k段的LCS

$d_{i,j,k,0..1}$ 表示匹配到i,j,当前分成了k段,当前段是否连续

转移

1
2
3
4
5
if(s1[i] == s2[j])
d[i][j][l][1] = max(d[i-1][j-1][l][1],d[i-1][j-1][l-1][0]) + 1;

d[i][j][l][0] = max(d[i-1][j][l][0],d[i][j-1][l][0]);
d[i][j][l][0] = max(d[i][j][l][0],d[i][j][l][1]);