合并回文子串（区间dp)

链接：合并回文子串
来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

输入两个字符串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

思路：

首先找出状态转移方程（主要是无论如果这个收尾相等的话，就找区间里面，首+1，尾-1），由于是bool型数组，所以用或，就是01得1 00得0 10得1 11得1（1为真，0为假），枚举下字符串长度，然后更新出最大值，记得初始化dp
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll t;
bool dp[55][55][55][55];
char a[55], b[55];
int main()
{
 cin >> t;
 while (t--)
 {
  int ans = -1;
  cin >> a + 1;
  cin >> b + 1;
  ll len1, len2;
  len1 = strlen(a + 1);
  len2 = strlen(b + 1);
  memset(dp, 0, sizeof(dp));
  for (int d1 = 0; d1 <= len1; d1++)//a中的字符串的长度
  {
   for (int d2 = 0; d2 <= len2; d2++)//b中的字符串的长度 
   {
    for (int i = 1, j = d1; j <= len1; i++, j++)
    {
     for (int k = 1, l = d2; l <= len2; k++, l++)
     {
      if (d1 + d2 <= 1)dp[i][j][k][l] = 1;//只有一个字符，所以一定是回文串 
      else
      {
       if (d1>1 && a[i] == a[j])dp[i][j][k][l] |= dp[i + 1][j - 1][k][l];
       if (d2>1 && b[k] == b[l])dp[i][j][k][l] |= dp[i][j][k + 1][l - 1];
       if (d1&&d2&&a[i] == b[l])dp[i][j][k][l] |= dp[i + 1][j][k][l - 1];
       if (d1&&d2&&b[k] == a[j]) 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;
}