一、题目描述
NC13230
输入两个字符串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的价值。
二、思路
区间dp
1.dp数组的下标及其定义：
用四维ijkl来表示状态，dp[i][j][k][l]的定义为字符串a中ij区间能否和字符串b中kl区间组成回文串
2.状态转移方程：
四种情况分别是：a[j] == a[i], a[j] == b[k], b[l] == a[i], b[l] == b[k]
因此就有四条性质类似的方程:
往a[i + 1] ~ a[j - 1] 与 b[k] ~ b[l] 两端加入a[i] 和 a[j]
if(dp[i + 1][j - 1][k][l]) dp[i][j][k][l] = 1;
往a[i] ~ a[j - 1] 与 b[k + 1] ~ b[l] 两端加入b[k] 和 a[j]
if(dp[i][j - 1][k + 1][l]) dp[i][j][k][l] = 1;
往a[i + 1] ~ a[j] 与 b[k] ~ b[l - 1] 两端加入a[i] 和 b[l]
if(dp[i + 1][j][k][l - 1]) dp[i][j][k][l] = 1;
往a[i] ~ a[j] 与 b[k + 1] ~ b[l - 1] 两端加入b[k] 和 b[l]
if(dp[i][j][k + 1][l - 1]) dp[i][j][k][l] = 1;
3.遍历顺序
要将每种情况遍历到，用四层循环，第一层是a字符串的回文串长度，第二层是b字符串的回文串长度，第三层是a的左右端点i，j，第四层是b的左右端点k，l
4.dp数组如何初始化
开始时先全初始化为0，在遍历时判断如果回文串长度是0的时候直接改成1就好，代表由单个字符组成的回文串
三、代码
#include<bits/stdc++.h>
using namespace std;
char a[100], b[100];
int dp[110][110][110][110];
int main(){
int t;
cin >> t;
while(t --){
scanf("%s", a + 1);
scanf("%s", b + 1);
memset(dp, 0, sizeof dp);
int ans = 0;
int lena = strlen(a + 1), lenb = strlen(b + 1);
for(int d1 = 0; d1 <= lena; d1 ++){ //d1为选取的a字符串中的长度
for(int d2 = 0; d2 <= lenb; d2 ++){ //d2为选取的b字符串中的长度
for(int i = 1, j = d1; j <= lena; i ++, j ++){ //i, j为a字符串所选区间的左右端点
for(int k = 1, l = d2; l <= lenb; k ++, l ++){ //k, l为b字符串所选区间的左右端点
if(d1 + d2 <= 1) dp[i][j][k][l] = 1; //只有单个字符作为回文串
else {
if(a[j] == a[i] && d1 > 1){
if(dp[i + 1][j - 1][k][l]) dp[i][j][k][l] = 1; //判断i + 1~j - 1段与k ~ l段能否组成回文串, 以下同理
}
if(a[j] == b[k] && d1 && d2){
if(dp[i][j - 1][k + 1][l]) dp[i][j][k][l] = 1;
}
if(b[k] == b[l] && d2 > 1){
if(dp[i][j][k + 1][l - 1]) dp[i][j][k][l] = 1;
}
if(b[l] == a[i] && d1 && d2){
if(dp[i + 1][j][k][l - 1]) dp[i][j][k][l] = 1;
}
}
//cout << dp[i][j][k][l];
if(dp[i][j][k][l]) ans = max(ans, d1 + d2);
}
//cout << endl;
}
}
}
cout << ans << endl;
}
return 0;
}