【每日一题】合并回文子串 (dp / 字符串 回文)

Solution
安利一下我的线性dp博客：https://blog.csdn.net/JiangHxin/article/details/105184169
一般情况下，动态规划的解题步骤是：
第一步：根据原问题和子问题来确定状态（dp数组表示什么东西）
第二步：根据状态确定状态转移方程（怎样求解dp数组 递推?dfs?）
第三步：确定要不要优化和编程实现方式 （单调队列?线段树?）

而字符串的话：
像回文串： 为字符串 的第 i 个字符到第 j 个字符的最长回文子序列长度。
特殊的：

一般的：

即两个串的匹配可以用来表示s1的前 i 个字符与s2的前 j 个字符的最大匹配。
但是这道题是求两个串组成的最大回文，所以考虑用

表示前s1的第 i 个字符到第 j 个字符 s2的第 k 个字符到第 l 个字符能否组成一个回文串。

Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }

const int manx=60;
const int mo=998244353;

ll dp[manx][manx][manx][manx];
char a[manx],b[manx];

int main()
{
    ll p=read();
    while(p--){
        cin>> a+1 >> b+1;
        ll n1=strlen(a+1),n2=strlen(b+1);
        ll ans=0;
        for(ll l1=0;l1<=n1;l1++)
            for(ll l2=0;l2<=n2;l2++)
                for(ll i=1;i+l1-1<=n1;i++)
                    for(ll k=1;k+l2-1<=n2;k++){
                        ll j=i+l1-1,l=k+l2-1;
                        if(l1+l2<=1) dp[i][j][k][l]=1;
                        else{
                            dp[i][j][k][l]=0;
                            if(a[i]==a[j]&&l1>1) dp[i][j][k][l]|=dp[i+1][j-1][k][l];
                            if(b[k]==b[l]&&l2>1) dp[i][j][k][l]|=dp[i][j][k+1][l-1];
                            if(l1&&l2){
                                if(a[i]==b[l]) dp[i][j][k][l]|=dp[i+1][j][k][l-1];
                                if(a[j]==b[k]) dp[i][j][k][l]|=dp[i][j-1][k+1][l];
                            }
                        }
                        if(dp[i][j][k][l]) ans=max(ans,l1+l2);
                    }
        cout<<ans<<endl;
    }
    return 0;
}