题目链接

合并回文子串

题目思路：区间dp

一个回文子串s[i][j]的子串s[i+1][j-1]必为回文子串，输入时注意从1开始输出，不然还要设边界条件，防止dp数组溢出

通过代码

#include<bits/stdc++.h>
using namespace std;
bool dp[55][55][55][55];
char s1[55],s2[55];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%s",s1+1);
        scanf("%s",s2+1);
        int n=strlen(s1+1),m=strlen(s2+1);
        int ans=0;
        memset(dp,0,sizeof(dp));
        for(int len1=0;len1<=n;len1++)
        for(int len2=0;len2<=m;len2++)
        for(int i=1;i+len1-1<=n;i++)
        for(int k=1;k+len2-1<=m;k++)
        {
            int j=i+len1-1,l=k+len2-1;
            if(len1+len2<=1)
                dp[i][j][k][l]=1;
            else
            {
                dp[i][j][k][l]=0;
                if(len1>1)
                    dp[i][j][k][l]|=(dp[i+1][j-1][k][l] && s1[i]==s1[j]);
                if(len2>1)
                    dp[i][j][k][l]|=(dp[i][j][k+1][l-1] && s2[k]==s2[l]);
                if(len1&&len2)
                    dp[i][j][k][l]|=(dp[i+1][j][k][l-1] && s1[i]==s2[l]);
                if(len1&&len2)
                    dp[i][j][k][l]|=(dp[i][j-1][k+1][l] && s1[j]==s2[k]);
            }
            if(dp[i][j][k][l])
                ans=max(ans,len1+len2);
        }
        cout<<ans<<endl;
    }
    return 0;
}