【每日一题】合并回文子串、区间DP

题目：https://ac.nowcoder.com/acm/problem/13230

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

————————————————————————————————

被虐了=='

dp方程参考的大佬的（https://blog.nowcoder.net/n/6a7de4febd824227ad7a32e9f429bcaf）

平时做过二维区间dp，石头合并经典题，写过区间dp的板子

所以知道实现的时候肯定是四个for循环。枚举所有的ijkl；

basecase是：当只选出一个字符，肯定是回文

【心得】

区间DP不咋熟，看来得练习区间DP，多写写就知道套路了

状态的表示不是直接表示为最长长度，而是表示为能否构成回文（bool）,然后看所有能构成的里面的最长长度====

写代码的时候注意一点：因为i-1 j-1这种涉及到-1下标，比较简单的处理是让字符串的下标从1开始

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
#define MAXN 55
int main(void)
{
    int T;cin>>T;
    int dp[MAXN][MAXN][MAXN][MAXN];//状态：s1中选i~j,s2中选k~l是否可以构成回文串
    while(T--){
        char s1[maxn],s2[maxn];
        scanf("%s",s1+1);scanf("%s",s2+1);
        memset(dp,0,sizeof(dp));
        int ans=0;
        int len1=strlen(s1+1);int len2=strlen(s2+1);
        for(int gap1=0;gap1<=len1;++gap1){
            for(int gap2=0;gap2<=len2;++gap2)
                for(int i=1;i<=len1-gap1+1;++i)
                    for(int k=1;k<=len2-gap2+1;++k){
                        int j=i+gap1-1;int l=k+gap2-1;
                        if(gap1+gap2<=1) {
                            dp[i][j][k][l]=1;
                            ans=max(ans,gap1+gap2);
                            continue;
                        }
                        if(s1[i]==s1[j]) dp[i][j][k][l] |= dp[i+1][j-1][k][l];
                        if(s2[k]==s2[l]) dp[i][j][k][l] |= dp[i][j][k+1][l-1];
                        if(s1[i]==s2[l]) dp[i][j][k][l] |= dp[i+1][j][k][l-1];
                        if(s1[j]==s2[k]) dp[i][j][k][l] |= dp[i][j-1][k+1][l];
                        if(dp[i][j][k][l]) ans=max(ans,gap1+gap2);   
                    }
        }
        cout << ans << endl;             
    }
    
    return 0;
}