nowcoder 合并回文子串

链接：https://www.nowcoder.com/acm/contest/6/C
来源：牛客网
题目
输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可

输入

第一行一个整数T(T ≤ 50)。
接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。

输出

对于每组数据输出一行一个整数表示价值最大的C的价值。

Input

2

aa

bb

a

aaaabcaa

Output

4

5

#include <bits/stdc++.h>

using namespace std;

const int N = ;

const int INF = 0x3f3f3f3f;

char a[N], b[N];

int dp[N][N][N][N];

int main ()

{

    int T; scanf("%d", &T);

    while(T--) {

        memset(dp,,sizeof(dp));

        scanf("%s%s", a+, b+);

        int l1 = strlen(a+), l2 = strlen(b+);

        int ans = ;

        for(int len1=; len1 <= l1; len1++)

        {

            for(int len2=; len2 <= l2; len2++)

            {

                for(int i=, j=i+len1-;j <= l1; i++,j++)

                {

                    for(int k=,l=k+len2-; l <= l2; k++,l++)

                    {

                        if(len1 ==  && len2 == )

                            dp[i][j][k][l] = ;

                        else if((len1 ==  && len2 == ) || (len1 ==  && len2 == ))

                            dp[i][j][k][l] = ;

                        else

                        {

                            dp[i][j][k][l] = -INF;

                            if(i<j && a[i] == a[j]) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i+][j-][k][l] + );

                            if(k<l && b[k] == b[l]) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k+][l-] + );

                            if(i<=j && k<=l && a[i]== b[l]) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i+][j][k][l-]+);

                            if(i<=j && k<=l && a[j] == b[k]) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-][k+][l]+);

                            ans = max(ans, dp[i][j][k][l]);

                        }

                    }

                }

            }

        }

        printf("%d\n", ans);

    }

    return ;

}

巴特西

nowcoder 合并回文子串

最新文章

热门文章