描述

给定两个字符串a和b，将两个字符串合并为c，要求两个字符串内部的顺序不变，求c的最长回文子串最大为多大

思路

• 区间dp的入门题目，设$dp[la][ra][lb][rb]dp[la][ra][lb][rb]$表示考虑字符串a的$[la,ra)[la,ra)$和字符串b的$[lb,rb)[lb,rb)$，能否组成一个回文字符串，则转移方程为

• 最终答案为满足$dp[la][ra][lb][rb]dp[la][ra][lb][rb]$为$truetrue$的$max(ra-la+rb-lb)max(ra-la+rb-lb)$
• 注意各种边界情况的处理

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
char a[MAXN],b[MAXN];
bool vis[MAXN][MAXN][MAXN][MAXN];
int n,m;
void dfs(int la,int ra,int lb,int rb,int &ans)
{
    
    if(la<1||lb<1||ra>n+1||rb>m+1)
        return ;
    if(vis[la][ra][lb][rb])
        return ;
    vis[la][ra][lb][rb]=true;
    ans=max(ans,ra-la+rb-lb);
    if(la>1&&ra<=n&&a[la-1]==a[ra])
        dfs(la-1,ra+1,lb,rb,ans);
    if(la>1&&rb<=m&&a[la-1]==b[rb])
        dfs(la-1,ra,lb,rb+1,ans);
    if(lb>1&&rb<=m&&b[lb-1]==b[rb])
        dfs(la,ra,lb-1,rb+1,ans);
    if(lb>1&&ra<=n&&b[lb-1]==a[ra])
        dfs(la,ra+1,lb-1,rb,ans);
}
void solve()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(vis,0,sizeof(vis));
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    int ans=0;
    for(int i=1;i<=n+1;i++)
        for(int j=1;j<=m+1;j++)
        {
            dfs(i,i,j,j,ans);
            dfs(i,i,j,j+1,ans);
            dfs(i,i+1,j,j,ans);
        }
    printf("%d\n",ans);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
}

时间复杂度$O(n^4)O(n^4)$，空间复杂度$O(n^4)O(n^4)$