【牛客活动每日一题】合并回文子串【区间dp】

合并回文子串

活动地址：https://ac.nowcoder.com/discuss/391086?type=101

思路

这是一道比较典型的区间dp题目，而区间dp很多时候都是小区间算好了结果，看能不能在此基础上更新大区间，这题也是如此。
这里我做了图解：
图片说明
所以我们只需要把初始化工作做好，然后推下去就好。也就是把字符串长度为0和1的f[i,j][l,r] 设置成true就行了

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T;
bool f[55][55][55][55];
char s1[55],s2[55];
int main(){
    cin>>T;
    while(T--){
        memset(f, false,sizeof f);
        int mx = 0;
        scanf("%s %s",s1+1,s2+1);
        int len1 = strlen(s1+1),len2 = strlen(s2+1);
        for(int L1 = 0;L1<=len1;L1++){
            for(int L2 = 0;L2<=len2;L2++){
                for(int i = 1;i<=len1-L1+1;i++){
                    for(int l = 1;l<=len2-L2+1;l++){
                        int j = i+L1-1,r = l+L2-1;
                        bool &t = f[i][j][l][r]; //用引用方便些
                        if(L1+L2 <= 1) t = true; //初始化工作
                        else{//这里改变了一下，跟图片中倒着想一想就知道了
                            if(s1[i] == s1[j]) t |= f[i+1][j-1][l][r];
                            if(s2[l] == s2[r]) t |= f[i][j][l+1][r-1];
                            if(s1[i] == s2[r]) t |= f[i+1][j][l][r-1];
                            if(s1[j] == s2[l]) t |= f[i][j-1][l+1][r];
                        }
                        if(t) mx = max(mx,L1+L2);
                    }
                }
            }
        }
        printf("%d\n",mx);
    }

    return 0;
}