合并回文子串

题目大意：

有两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。需要求出所有可能的C中长度最大的回文子串（这里的字串是指连续的），输出这个最大长度即可

算法过程

嗯，区间dp。以前没写过。学会了区间dp要按长度枚举。
dp[i][j][k][l]表示A的（i，j）与B的（k，l）区间内的字符是否能合并为一个回文串
状态转移：

   if(A[i]==A[j]&&dp[i+1][j-1][k][l])   dp[i][j][k][l]=1;
   if(A[i]==B[l]&&dp[i+1][j][k][l-1])  dp[i][j][k][l]=1;
   if(B[k]==B[l]&&dp[i][j][k+1][l-1])  dp[i][j][k][l]=1;
   if(B[k]==A[j]&&dp[i][j-1][k+1][l])  dp[i][j][k][l]=1;

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> P;
const int INF=0x3f3f3f3f;
const LL LINF=0x3f3f3f3f3f3f;
const int MAX_N=1e5+20;
const LL MOD=1e9+7;
int T;
char A[55],B[55];
int a,b;
bool dp[55][55][55][55];
void solve(){
    memset(dp,0,sizeof(dp));
    int ans=0;
    for(int len1=0;len1<=a;len1++){
        for(int len2=0;len2<=b;len2++){
            for(int i=1;i+len1-1<=a;i++){
                for(int k=1;k+len2-1<=b;k++){
                    int j=i+len1-1,l=k+len2-1;
                    if(len1+len2<=1)    dp[i][j][k][l]=1;
                    else{
                        if(A[i]==A[j]&&dp[i+1][j-1][k][l])  dp[i][j][k][l]=1;
                        if(A[i]==B[l]&&dp[i+1][j][k][l-1])  dp[i][j][k][l]=1;
                        if(B[k]==B[l]&&dp[i][j][k+1][l-1])  dp[i][j][k][l]=1;
                        if(B[k]==A[j]&&dp[i][j-1][k+1][l])  dp[i][j][k][l]=1;
                    }
                    if(dp[i][j][k][l])  ans=max(ans,len1+len2);
                }
            }
        }
    }
    printf("%d\n",ans);
}
int main(){
    //freopen("1.txt", "r", stdin);
    //ios::sync_with_stdio(false);
    //cin.tie(0),cout.tie(0);
    scanf("%d",&T);
    while(T--){
        scanf("%s",A+1);
        scanf("%s",B+1);
        a=strlen(A+1),b=strlen(B+1);
        solve();
    }
}