牛客 - 13230 合并回文子串

传送门：牛客 - 13230

思路分析

考虑 $c$ 中的回文子串，既然是子串，就一定可以拆成 $a$, $b$ 两串的两个子串的 combine。不妨 设是 $a[i, j]$与 $b[k, l]$的 combine，则可以考虑动态规划的状态 $f[i][j][k][l]$表示 $a[i, j]$与 $b[k, l]$的 combine 能否组成回文子串。 则可以匹配第一个字符和最后一个字符来转移，根据第一个字符和最后一个字符分别来自 $a$ 还是 $b$ 共有四种转移:

1. $f[i][j][k][l]<-f[i+1][j-1][k][k]$ $(i<j,a[i]=a[j])$
2. $f[i][j][k][l]<-f[i+1][j][k][l-1]$ $(i<=j,k<=l,a[i]=b[l])$
3. $f[i][j][k][l]<-f[i][j-1][k+1][l]$ $(i<=j,k<=l,a[j]=b[k])$
4. $f[i][j][k][l]<-f[i][j][k+1][l-1]$ $(k<l,b[k]=b[l])$

注意边界情况，新串长度小于等于1的时候，为true

样例输入

2
aa
bb
a
aaaabcaa

样例输出

4
5

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;

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

int main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    cin>>t;
    while(t--) {
        scanf("%s%s",a+1,b+1);
        int n1=strlen(a+1);
        int n2=strlen(b+1);
        int ans=-INF;
        for(int len1=0; len1<=n1; len1++) {
            for(int len2=0; len2<=n2; len2++) {
                for(int i=1,j=len1+i-1; j<=n1; i++,j++) {
                    for(int k=1,l=len2+k-1; l<=n2; k++,l++) {
                        if(len1+len2<=1) dp[i][j][k][l]=1;
                        else {
                            dp[i][j][k][l]=0;
                            if(len1>1 && a[i]==a[j]) dp[i][j][k][l]|=dp[i+1][j-1][k][l];
                            if(len2>1 && b[k]==b[l]) dp[i][j][k][l]|=dp[i][j][k+1][l-1];
                            if(len1 && len2 && a[i]==b[l]) dp[i][j][k][l]|=dp[i+1][j][k][l-1];
                            if(len1 && len2 && 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,j-i+1+l-k+1);
                    }
                }
            }
        }
        cout<<ans<<endl;
    }



    return 0;
}