【每日一题】合并回文子串

戳我传送
题意：

思路：
区间dp， 表示a串的第i个字符到第j个个字符和b串第k个字符到第l个字符组成的串能否构成回文串，求法通过分解代码的形式分析，因为这个思路对我来说有点难。

for(int len1=0;len1<=n;++len1)
for(int len2=0;len2<=m;++len2)
for(int i=1;i+len1-1<=n;++i)
for(int k=1;k+len2-1<=m;++k)

这里是枚举区间长度和起点，然后根据区间长度和起点可以退出终点，len1<=n很好理解，因为终点j=i+len1-1不能大于n，所以i+len1-1<=n，len2也是一个道理。

int j=i+len1-1,l=k+len2-1;

计算a串区间的右端点j，b串区间的右端点l，特别当长度为0时，右端点=左端点-1。

if(len1+len2<=1) f[i][j][k][l]=true;
else {
    f[i][j][k][l]=false;
    if(len1>1) f[i][j][k][l] |= (f[i+1][j-1][k][l]&&a[i]==a[j]);
    if(len1 && len2) f[i][j][k][l] |= (f[i+1][j][k][l-1] && (a[i]==b[l]));
    if(len1 && len2) f[i][j][k][l] |= (f[i][j-1][k+1][l] && (a[j]==b[k]));
    if(len2>1) f[i][j][k][l] |= (f[i][j][k+1][l-1] && (b[k]==b[l]));
}

if(len1+len2<=1) f[i][j][k][l]=true;

如果只有a串提供一个字符、b串提供一个字符或者都不提供字符，那么一定是回文串，这是边界情况。

if(len1>1) f[i][j][k][l] |= (f[i+1][j-1][k][l]&&a[i]==a[j]);
if(len2>1) f[i][j][k][l] |= (f[i][j][k+1][l-1]&&b[k]==b[l]);

， ，因为回文串可以是a、b串交叉形成的，也就是可能a、b选出某个区间的字符组成回文串后，两端加上a串该区间的前一个字符和后一个字符，且这两个字符相等，那么新形成的串还是回文串。第二行和第一行一样的就不讲了。

if(len1 && len2) f[i][j][k][l] |= (f[i+1][j][k][l-1] && (a[i]==b[l]));
if(len1 && len2) f[i][j][k][l] |= (f[i][j-1][k+1][l] && (a[j]==b[k]));

理解了上面的一段后这两行代码也就简单了，有点迷惑的就是为什么不考虑前面的状态 ，因为要形成的是回文串，所以 和 是一样的，如果可以构成回文串，那么这种情况a提供的字符左右颠倒完全没区别，如果构不成，那就更每影响了。

if(f[i][j][k][l]) ans=max(ans,len1+len2);

如果a、b串提供的字符能组成回文串，那么这就是一个答案，维护最大的答案即可。
Code：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=101;
char a[maxn],b[maxn];
bool f[maxn][maxn][maxn][maxn];
int t,n,m;
int main() {
    scanf("%d",&t);
    while(t--) {
        int ans=0;
        scanf("%s%s",a+1,b+1);
        n=strlen(a+1);
        m=strlen(b+1);
        for(int len1=0;len1<=n;++len1)
        for(int len2=0;len2<=m;++len2)
        for(int i=1;i+len1-1<=n;++i)
        for(int k=1;k+len2-1<=m;++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;
                if(len1>1) f[i][j][k][l] |= (f[i+1][j-1][k][l]&&a[i]==a[j]);
                if(len1&&len2) f[i][j][k][l] |= (f[i+1][j][k][l-1]&&a[i]==b[l])|(f[i][j-1][k+1][l]&&a[j]==b[k]);
                if(len2>1) f[i][j][k][l] |= (f[i][j][k+1][l-1]&&b[k]==b[l]);
            }
            if(f[i][j][k][l]) ans=max(ans,len1+len2);
        }
        printf("%d\n",ans);
    }
}