【每日一题】合并回文子串

有一说一这题对我来说难度还是挺大的，看了大佬的题解才懂得，确实还是个dp小白
思路：
用dp[i][k][j][l]表示 第一个串从i到k位置 和第二个串从j到l位置是不是可以组成回文串
是的话值为1，否则为0

那么考虑转移
有2*2种 (两个头 两个尾)

a[i]==a[k] dp[i][k][j][l] |= dp[i+1][k-1][j][l] 这里要注意k-i+1 也就是长度需要≥2 因为i和k代表不同位置
b[j]==b[l] dp[i][k][j][l] |= dp[i][k][j+1][l-1] 这里要注意l-j+1 也就是长度需要≥2 理由同上*
b[j]==a[k] dp[i][k][j][l] |= dp[i][k-1][j+1][l] 保证串长度不为0即可
a[i]==b[l] dp[i][k][j][l] |= dp[i+1][k][j][l-1] 同上

边界的话 只要长度之和加起来≤1 那么dp[i][k][j][l]一定为1

#include<bits/stdc++.h>
using namespace std;
bool dp[55][55][55][55];
char a[55],b[55];
int main(){
    ios::sync_with_stdio(0);
    int t;cin>>t;
    while(t--){
        int ans=1;
        cin>>a+1>>b+1;
        int la=strlen(a+1),lb=strlen(b+1);
        for(int l1=0;l1<=la;l1++){///枚举第一个串长度
            for(int l2=0;l2<=lb;l2++){///枚举第二个串长度
                for(int i=1;i+l1-1<=la;i++){///枚举第一个串起点
                    for(int j=1;j+l2-1<=lb;j++){///枚举第二个串起点
                        int k=i+l1-1,l=j+l2-1;///终点
                        if(l1+l2<=1) dp[i][k][j][l]=1;///其中一个为不选 另一个选一个
                        else{
                            dp[i][k][j][l]=0;
                            if(a[i]==a[k]&&l1>1) dp[i][k][j][l] |=dp[i+1][k-1][j][l];///a[i]加在头 a[k]加在尾
                            if(b[j]==b[l]&&l2>1) dp[i][k][j][l] |=dp[i][k][j+1][l-1];///b[j]加在头 b[l]加在尾
                            if(a[i]==b[l]&&l1&&l2) dp[i][k][j][l] |=dp[i+1][k][j][l-1];///a[i]加在头 b[l]加在尾
                            if(b[j]==a[k]&&l1&&l2) dp[i][k][j][l] |=dp[i][k-1][j+1][l];///b[j]加在头 a[k]加在尾
                        }
                        if(dp[i][k][j][l]){
                            ans=max(ans,l1+l2);
                        }
                    }
                }
            }
        }
    cout<<ans<<endl;
    }
    return 0;
}