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

题意：
给定两个字符串a和b，从a和b中选取若干元素，不改变其在原字符串中的顺序，求能够形成的回文串的最大长度。
思路：
区间dp。
用dp[i][j][k][l]表示从a串选取第i个到第j个元素，从b串选取第k个到第l个元素，这些元素能否形成回文串。
可以这样考虑回文串的形成：一个回文串在两边加上相同的字符形成一个新的回文串。
因为要求不改变字符在原串的顺序，所以两边加上的字符有以下几种可能：
a[i]-a[j] a[i]-b[l] b[k]-a[j] b[k]-b[l]；
得到以下状态转移方程：
dp[i][j][k][l]|=(a[i]==a[j])&&dp[i+1][j-1][k][l];
dp[i][j][k][l]|=(a[i]==b[l])&&dp[i+1][j][k][l-1];
dp[i][j][k][l]|=(b[k]==a[j])&&dp[i][j-1][k+1][l];
dp[i][j][k][l]|=(b[k]==b[l])&&dp[i][j][k+1][l-1];
对于边界的处理：只要两个串选择的字符个数为1，dp就为1。
区间dp要从短区间扩展到长区间，所以要枚举区间的长度而不是首末端点。
代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> Q;
const int inf=2e9+9;
const int maxn=1e6+9;
const int maxx=2e5+9;

char a[55],b[55];
int dp[55][55][55][55];

int main()
{
    int t; cin>>t;
    while(t--)
    {
        cin>>a+1>>b+1;
        memset(dp,0,sizeof dp);
        int l1=strlen(a+1),l2=strlen(b+1);
        int res=0;
        for(int len1=0;len1<=l1;len1++)
        for(int len2=0;len2<=l2;len2++)
        for(int i=1;i+len1-1<=l1;i++)
        for(int k=1;k+len2-1<=l2;k++)
        {
            int j=i+len1-1,l=k+len2-1;
            if(j+l-k-i+2<=1) dp[i][j][k][l]=1;
            else
            {
                dp[i][j][k][l]|=(a[i]==a[j])&&dp[i+1][j-1][k][l];
                dp[i][j][k][l]|=(a[i]==b[l])&&dp[i+1][j][k][l-1];
                dp[i][j][k][l]|=(b[k]==a[j])&&dp[i][j-1][k+1][l];
                dp[i][j][k][l]|=(b[k]==b[l])&&dp[i][j][k+1][l-1];
            }
            if(dp[i][j][k][l]) res=max(res,len1+len2);
        }
        cout<<res<<endl;
    }
}