题目描述：

输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。 我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可

题解

首先考虑单独字符串如何判断子区间是否为回文，容易知道两维dp即可维护。
简易代码： dp[i][j] = (a[i] == a[j]) ? dp[i + 1][j - 1]:0
那么回到本题，我们可以增加dp的维度便可以模仿上述转移。代码如下：
if(a[i]==a[j]) dp[i][j][k][l] |= dp[i+1][j-1][k][l];
if(a[i]==b[l]) dp[i][j][k][l] |= dp[i+1][j][k][l-1];
if(b[k]==b[l]) dp[i][j][k][l] |= dp[i][j][k+1][l-1];
if(b[k]==a[j]) dp[i][j][k][l] |= dp[i][j-1][k+1][l];
dp[i][j][k][l]表示a数组的i-j区间和b数组的k-l区间是否能够构成回文数组。 最后特判一下恒成立的区间即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 55;
char a[N], b[N];
bool f[N][N][N][N];
int T;

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> (a + 1) >> (b + 1);
        //memset(f, 0, sizeof f);

        int ans = 1;
        for (int la = 0; la <= strlen(a+1); la ++)
            for (int lb = 0; lb <= strlen(b+1); lb ++)
                for (int l1 = 1; l1 + la - 1 <= strlen(a+1); l1 ++)
                    for (int l2 = 1; l2 + lb - 1 <= strlen(b+1); l2 ++)
                    {
                        int r1 = l1 + la - 1, r2 = l2 + lb - 1;
                        if(la + lb <= 1) f[l1][r1][l2][r2] = 1;
                        else
                        {
                            f[l1][r1][l2][r2] = 0;
                        //cout << " " <<l1  <<" " <<r1<<" " << l2 << " " << r2 << endl;
                        //cout << f[l1][r1][l2][r2] << endl;
                            if(a[l1]==a[r1]) f[l1][r1][l2][r2] |= f[l1 + 1][r1 - 1][l2][r2];
                            if(b[l2]==b[r2]) f[l1][r1][l2][r2] |= f[l1][r1][l2 + 1][r2 - 1];
                            if(a[l1]==b[r2]) f[l1][r1][l2][r2] |= f[l1 + 1][r1][l2][r2 - 1];
                            if(b[l2]==a[r1]) f[l1][r1][l2][r2] |= f[l1][r1 - 1][l2 + 1][r2];
                        }
                        //cout << f[l1][r1][l2][r2] << endl;
                        if(f[l1][r1][l2][r2]) ans = max(ans, la + lb);
                    }
        cout << ans << endl;
    }
}