D. Alyona and Strings

题意

给出两个字符串s,t，让找出最长的k个在s,t不相交的公共子串。

思路

看了好几个题解才搞懂。

代码中有注释

代码

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;

const int N=1e5+10;

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

char s[N],t[N],k;

int dp[1010][1010][11][2];

/*

终于搞明白了

dp[i][j][k][0]表示的是s的前i个字符，t的前j个字符，选择k个公共子串的最大值（不一定包括i,j）

dp[i][j][k][1]表示的是s的前i个字符，t的前j个字符，选择k个公共子串最后是i,j的最大值

dp[lens][lent][k][0]就是题目要求的答案。

当s[i]==t[j]的时候dp[i][j][k][1]才存在（不为0）

*/

int main()

{

    int lens,lent;

    scanf("%d%d%d%s%s",&lens,&lent,&k,s+1,t+1);

    for(int i=1; i<=lens; i++)

    {

        for(int j=1; j<=lent; j++)

        {

            for(int l=1; l<=k; l++)

            {

                if(s[i]==t[j])//只有s[i]==t[j]的时候才有dp[i][j][l][1]

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

                /*可以沿用之前的第l个公共子串，或者让i，j作为第l个子串的第一位*/

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

            }

        }

    }

    printf("%d\n",dp[lens][lent][k][0]);

    return 0;

}

/*

*/

巴特西

CF#358 D. Alyona and Strings DP

D. Alyona and Strings

题意

思路

代码

最新文章

热门文章