CF #358 D. Alyona and Strings

正文索引 [隐藏]

传送门:http://codeforces.com/contest/682/problem/D

题目大意

有两个串A&B,我们要在A串中寻找k个不相交的子串,使B串中的也存在同样顺序不相交的这样k个子串。求子串总长度的最大值。

题解

我们考虑F[k][i][j],表示已经做到了第K个部分,现在A串拍到了第i位,B串拍到了第j位,所能达到的最长总长度。
首先是Naive的分析转移

  1. F[k][i][j]可以由F[k][i-1][j]与F[k][i][j-1]直接转移得到
  2. 如果A[i]=B[j],那么F[k][i][j]可以由F[k-1][i-1][j-1]+1转移
  3. 这是时候,我们发现漏了一个转移,那就是k不变,F[k][i][j]由F[k][i-1][j-1]得到,但是由于1转移,我们这样会使得不连续的情况也当做连续的情况处理,所以我们考虑增设一个P[k][i][j]

接下来是正式的分析,F[k][i][j]表示已经做到了第K个部分,现在A串拍到了第i位,B串拍到了第j位,所能达到的最长总长度。P[k][i][j]表示已经做到了第K个部分,现在A串拍到了第i位且第i位被使用,B串拍到了第j位且第j位被使用,所能达到的最长总长度。然后如下转移

  1. 如果A[i]=B[i],P[k][i][j] = max( F[k-1][i-1][j-1] , P[k][i][j] );
  2. F[k][i][j] = max( F[k][i][j-1] , F[k][i-1][j] , P[k][i][j] );

代码