链接：https://ac.nowcoder.com/acm/problem/13230
来源：牛客网

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

输入描述:
第一行一个整数T(T ≤ 50)。
接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。

输出描述:
对于每组数据输出一行一个整数表示价值最大的C的价值。

输入
2
aa
bb
a
aaaabcaa

输出
4
5

Solution

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
bool dp[55][55][55][55];
int main(){
  string s, t;
  int test;
  cin >> test;
  while(test--){
    memset(dp, 0, sizeof(dp));
    cin >> s >> t;
    s = " " + s, t = " " + t; // 让下标从1开始 方便处理
    int ans = 0;
    int s_len = s.size() - 1, t_len = t.size() - 1;
    for(int len1 = 0; len1 <= s_len; len1++){ // 枚举 s 串的贡献
      for(int len2 = 0; len2 <= t_len; len2++){  // 枚举 t 串的贡献
        for(int l1 = 1, r1 = l1 + len1 - 1; r1 <= s_len; r1++, l1++){ // 截取一段 s 中长度为 len1 的子串
          for(int l2 = 1, r2 = l2 + len2 - 1; r2 <= t_len; r2++, l2++){ // 截取一段 t 中长度为 len2 的子串
            if(len1 + len2 <= 1){
              dp[l1][r1][l2][r2] = 1; // 单个字符是回文串
            }       
            else {
              if(s[l1] == s[r1] && r1 > 0){ // 这个 s 的子串的首尾相同
                dp[l1][r1][l2][r2] |= dp[l1 + 1][r1 - 1][l2][r2]; // 1.由 l1 + 1 -> r1 - 1 扩展为 l -> r
              }
              if(s[l1] == t[r2] && r2 > 0){
                dp[l1][r1][l2][r2] |= dp[l1 + 1][r1][l2][r2 - 1]; // 2. 对于当前的串 前面加 s[l1], 后面加 t[r2];
              }
              if(t[l2] == t[r2] && r2 > 0){
                dp[l1][r1][l2][r2] |= dp[l1][r1][l2 + 1][r2 - 1]; // 同1
              }
              if(t[l2] == s[r1] && r1 > 0){
                dp[l1][r1][l2][r2] |= dp[l1][r1 - 1][l2 + 1][r2]; // 同2
              }
              if(dp[l1][r1][l2][r2]){
                ans = max(ans, r1 - l1 + 1 + r2 - l2 + 1); // 如果当前dp[l1][r1][l2][r2] 为true 说明为回文串 更新答案
              }
            }
          }
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}