Solution

看到数据范围可以想到区间。

由题意可知字串是连续的。设 为在 中选取 到 ，在 中选取 到 是否能构成回文串。转移方程如下：

• （，)
• （，)
• （，，)
• （，，）

利用或运算可以方便的转移。当两个字符串最多选出一个字符时，此时显然有 ，作为边界条件。

时间复杂度：。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,ans,dp[52][52][52][52];
string a,b;
int main(){
    cin>>n;
    int s,t;
    while(n--){
        memset(dp,0,sizeof(dp));
        ans=0;
        cin>>a>>b;
        s=a.size(),t=b.size();
        for(int x=0;x<=s;x++)
            for(int y=0;y<=t;y++)
                for(int i=1,j=x;j<=s;i++,j++)
                    for(int k=1,l=y;l<=t;k++,l++){
                        if(x+y<=1)
                            dp[i][j][k][l]=1;
                        else{
                            if(a[i-1]==a[j-1]&&x>1)
                                dp[i][j][k][l]|=dp[i+1][j-1][k][l];
                            if(b[k-1]==b[l-1]&&y>1)
                                dp[i][j][k][l]|=dp[i][j][k+1][l-1];
                            if(x&&y){
                                if(a[i-1]==b[l-1])
                                    dp[i][j][k][l]|=dp[i+1][j][k][l-1];
                                if(a[j-1]==b[k-1])
                                    dp[i][j][k][l]|=dp[i][j-1][k+1][l];
                            }
                        }
                        if(dp[i][j][k][l])
                            ans=max(ans,x+y);
                    }
        cout<<ans<<endl;
    }
    return 0;
}