loj 6163 「美团 CodeM 初赛 Round A」 合并回文子串

#include <bits/stdc++.h>
using namespace std;
const int maxn=50+5;
const int INF=0x3f3f3f3f;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int dp[maxn][maxn][maxn][maxn];
char a[maxn],b[maxn];
int T;
int main(){
    for (read(T);T;T--){
        scanf("%s",a+1);
        scanf("%s",b+1);
        int n=(int)strlen(a+1),m=(int)strlen(b+1);
        int ans=0;
        for (int lena=0;lena<=n;lena++){
            for (int lenb=0;lenb<=m;lenb++){
                for (int i=1,j=lena;j<=n;i++,j++){
                    for (int k=1,l=lenb;l<=m;k++,l++){
                        if (lena==0 && lenb==0) dp[i][j][k][l]=0;
                        else if ((lena==0 && lenb==1)||(lena==1 && lenb==0)) dp[i][j][k][l]=1;
                        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+1][j-1][k][l]+2);
                            if (k<l && b[k]==b[l]) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k+1][l-1]+2);
                            if (i<=j && k<=l && a[i]==b[l]) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i+1][j][k][l-1]+2);
                            if (i<=j && k<=l && a[j]==b[k]) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-1][k+1][l]+2);
                        }
                        ans=max(ans,dp[i][j][k][l]);
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}