题意

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

题解

遇到这种数据范围较小的计数问题应该优先考虑dp，本题就是如此。
那么应该怎么样考虑转移呢？
首先最后C中的那个价值最大的子串一定是由字符串A的一个区间和字符串B的一个区间合并得到的，
那么现在假设A[i] ~ A[j]与B[k] ~ B[l]构成了一个回文串(这里设dp[i][j][k][l])
则他能转移到的区间有
1：a[i-1]==a[j+1]时 dp[i-1][j+1][k][l]
2：a[i-1]==b[l+1]时 dp[i-1][j][k][l+1]
3：b[k-1]==a[j+1]时 dp[i][j+1][k-1][l]
4：b[k-1]==b[l+1]时 dp[i][j][k-1][l+1]
那么对应的转移方程就为

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];

然后就可以轻松的区间转移啦~
oh，在注意一下枚举过程中只有一个字母的状态一定是回文的就可以啦

代码

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;


const int N = 5e3+5;
const int mod =1e9+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e6+6;

int _,ans,la,lb,dp[55][55][55][55];
char a[maxn],b[maxn];

int main(){
    for(scanf("%d",&_);_;_--){
        scanf("%s",a+1);
        scanf("%s",b+1);
        la=strlen(a+1);lb=strlen(b+1);
        ans=0;
        for(int l1=0;l1<=la;l1++){
            for(int l2=0;l2<=lb;l2++){
                 for(int i=1;i<=la-l1+1;i++){
                    for(int k=1;k<=lb-l2+1;k++){
                        int j=i+l1-1,l=k+l2-1;
                        if(l1+l2<=1) dp[i][j][k][l]=1;
                        else {
                            dp[i][j][k][l]=0;
                            if(a[i]==a[j]) dp[i][j][k][l]|=dp[i+1][j-1][k][l];
                            if(b[k]==b[l]) dp[i][j][k][l]|=dp[i][j][k+1][l-1];

                            if(a[i]==b[l]) dp[i][j][k][l]|=dp[i+1][j][k][l-1];
                            if(b[k]==a[j]) dp[i][j][k][l]|=dp[i][j-1][k+1][l];
                        }
                        if(dp[i][j][k][l]) ans=max(ans,l1+l2);
                    }
                 }
            }
        }
        printf("%d\n",ans);

    }
}