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的分析转移
- F[k][i][j]可以由F[k][i-1][j]与F[k][i][j-1]直接转移得到
- 如果A[i]=B[j]，那么F[k][i][j]可以由F[k-1][i-1][j-1]+1转移
- 这是时候，我们发现漏了一个转移，那就是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位被使用，所能达到的最长总长度。然后如下转移
- 如果A[i]=B[i]，P[k][i][j] = max( F[k-1][i-1][j-1] , P[k][i][j] );
- F[k][i][j] = max( F[k][i][j-1] , F[k][i-1][j] , P[k][i][j] );
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include #include using namespace std; const int Maxn=1005; char A[Maxn],B[Maxn]; int n,m,K; int F[15][Maxn][Maxn]; int P[15][Maxn][Maxn]; int Ans=0; int main(){ scanf("%d%d%d",&n,&m,&K); scanf("%s%s",A+1,B+1); for (int k = 1 ; k <= K ; k++){ for (int i = 1 ; i <= n ; i++){ for (int j = 1 ; j <= m ; j++){ if ( A[i] == B[j] ){ P[k][i][j] = max ( P[k][i-1][j-1]+1 , F[k-1][i-1][j-1]+1 ); } F[k][i][j] = max( F[k][i-1][j] , F[k][i][j-1]); F[k][i][j] = max( F[k][i][j] , P[k][i][j]); } } } for (int k=1;k<=K;k++){ printf("#%d\n",k); for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ printf("%d ",P[k][i][j]); } printf("\n"); } } /*for (int k=1;k<=K;k++){ printf("#%d\n",k); for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ printf("%d ",F[k][i][j]); } printf("\n"); } }*/ printf("%d\n",F[K][n][m]); return 0; } |
原文链接：CF #358 D. Alyona and Strings
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!