NC13230

题意

输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可。
T(T ≤ 50)
A,B(|A|,|B| ≤ 50)

思路

数据范围感觉区间DP
区间DP切忌枚举的是区间的长度，而不能直接枚举端点，因为长度长的结果是由长度短的结果得出的。
难点在于表示a中i到j和b中k到l所组成的字符串是否为回文串，而不是区间的长度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 55;

bool f[N][N][N][N];
char a[N],b[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        int res=0;
        cin>>a+1>>b+1;
        int la=strlen(a+1),lb=strlen(b+1);
        for(int len1=0;len1<=la;len1++){
            for(int len2=0;len2<=lb;len2++){
                for(int i=1;i+len1-1<=la;i++){
                    for(int k=1;k+len2-1<=lb;k++){
                        int j=i+len1-1,l=k+len2-1;
                        if(len1+len2<=1) f[i][j][k][l]=true;
                        else{
                            f[i][j][k][l]=false;
                            f[i][j][k][l]|=(a[i]==a[j])&&(f[i+1][j-1][k][l]);
                            f[i][j][k][l]|=(a[i]==b[l])&&(f[i+1][j][k][l-1]);
                            f[i][j][k][l]|=(a[j]==b[k])&&(f[i][j-1][k+1][l]);
                            f[i][j][k][l]|=(b[k]==b[l])&&(f[i][j][k+1][l-1]);
                        }
                        if(f[i][j][k][l]){
                            res=max(res,len1+len2);
                        }
                    }
                }
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}