题号：NC13230
名称：合并回文子串
来源：美团2017年CodeM大赛-初赛A轮
题目链接

时间限制：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的价值。
示例1

输入

2
aa
bb
a
aaaabcaa

输出

4
5

思路：区间dp问题
dp[i][j][m][n]表示A中下标i到j-1以及B中下标m到n-1的串，能否组成回文串
(dp值为零则表示不构成回文串，不为零则表示构成)
首先：字符本身是回文串
其次，分为四种情况
a[i]==a[j-1] dp[i][j][m][n]+=c[i+1][j-1][m][n];
因为dp我们只考虑是否为0或非0，所以dp之间可以+=也可以|=,都不影响
（当A的第i为和第j-1位相同时，那么dp[i][j]是否为回文串就取决于比它小一层的dp[i+1][j-1]，这样一次往里推，就可以推到以一种情况）
b[m]==b[n-1] dp[i][j][m][n]+=c[i][j][m+1][n-1];
(和上一个思路相同)

a[i]==b[n-1] dp[i][j][m][n]+=c[i+1][j][m][n-1];
（当A的i与B的n-1相同时，那么dp[i][][][n]是否为回文串就取决于A的后一位i+1和B的前一位n-1的情况）
a[m]==b[j-1] dp[i][j][m][n]+=c[i][j-1][m+1][n];
代码

#include<bits/stdc++.h>
#define maxn 100
using namespace std;
int t;
char a[maxn],b[maxn];
int c[maxn][maxn][maxn][maxn];
int main()
{
    cin>>t;
    char ch=getchar();
    int j;
    int n;
    while(t--)
    {
        int ans=0;
        cin>>a;
        ch=getchar();
        cin>>b;
        ch=getchar();
        int len1=strlen(a),len2=strlen(b);
        for(int tj=0;tj<=len1;tj++)
        {
            for(int tn=0;tn<=len2;tn++)
            {
                for(int i=0;i+tj<=len1;i++)
                {
                    for(int m=0;m+tn<=len2;m++)
                    {
                        j=i+tj;
                        n=m+tn;
                        if(tj+tn<=1)c[i][j][m][n]=1;
                        else
                        {
                            c[i][j][m][n]=0;
                            if(tj>=2&&a[i]==a[j-1])c[i][j][m][n]|=c[i+1][j-1][m][n];                                               
                            if(tn>=2&&b[m]==b[n-1])c[i][j][m][n]|=c[i][j][m+1][n-1];
                            if(tj>=1&&tn>=1&&a[i]==b[n-1])c[i][j][m][n]|=c[i+1][j][m][n-1];
                            if(tj>=1&&tn>=1&&a[m]==b[j-1])c[i][j][m][n]|=c[i][j-1][m+1][n];
                        }
                        if(c[i][j][m][n])ans=max(ans,tj+tn);
                    }
                }
            }
         } 
        cout<<ans<<endl;
    }
    return 0;
}

另外
tj和tn从0开始，用于不断讨论A中i到i+tj和B中m到tn的回文字符串