题解 | #合并回文子串#

刚学的DP，写得比较烂，见谅下。

字符串判断是否回文，用区间DP描述应该是：当s[l] == s[r]时，dp[l,r] |= dp[l + 1,r - 1]; 只要它中间为回文串，当符合判断条件时，就也是回文串。

后来是判断两条字符串组合而成的字符串是否回文。前面我也没想到四维，看答案看到四维就返回去写了。

f[l1][r1][l2][r2];

字符串1：s1, 字符串2：s2.

if (s1[l1] == s1[r1]) dp[l1][r1][l2][r2] |= dp[l1 + 1][r1 - 1][l2][r2];

if (s1[l1] == s2[r2]) dp[l1][r1][l2][r2] |= dp[l1 + 1][r1][l2][r2 - 1];

if (s2[l2] == s1[r1]) dp[l1][r1][l2][r2] |= dp[l1][r1 - 1][l2 + 1][r2];

if (s2[l2] == s2[r2]) dp[l1][r1][l2][r2] |= dp[l1][r1][l2 + 1][r2 - 1];

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 60;
int dp[N][N][N][N];

int main ()
{
    int T;
    cin >> T;
    while (T --)
    {
        //memset(dp, 0, sizeof dp);//后面在初始化也行，省时间。
        string s1, s2;
        cin >> s1 >> s2;
        int size1 = s1.size(), size2 = s2.size();
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        int ans = 1;//答案至少也是1，所以ans初始化为1
        for (int len1 = 0; len1 <= size1; len1 ++)//区间DP的模板。区间从0开始，因为可能取零。
            for (int len2 = 0; len2 <= size2; len2 ++)
                for (int l1 = 1; l1 + len1 - 1 <= size1; l1 ++)
                    for (int l2 = 1; l2 + len2 - 1 <= size2; l2 ++)
                    {
                         int r1 = l1 + len1 - 1, r2 = l2 + len2 - 1;
                        if (len1 + len2 <= 1) dp[l1][r1][l2][r2] = 1;
                        else {
                            dp[l1][r1][l2][r2] = 0;//初始化
                            if (s1[l1] == s1[r1]) dp[l1][r1][l2][r2] |= dp[l1 + 1][r1 - 1][l2][r2];
                            if (s1[l1] == s2[r2]) dp[l1][r1][l2][r2] |= dp[l1 + 1][r1][l2][r2 - 1];
                            if (s2[l2] == s1[r1]) dp[l1][r1][l2][r2] |= dp[l1][r1 - 1][l2 + 1][r2];
                            if (s2[l2] == s2[r2]) dp[l1][r1][l2][r2] |= dp[l1][r1][l2 + 1][r2 - 1];
                        }
                        if (dp[l1][r1][l2][r2]) ans = max(ans, len1 + len2);
                        //cout << dp[l1][r1][l2][r2] << '\n';
                    }
        cout << ans << '\n';
    }
    return 0;
}