又见回文(区间dp)

题目：

题解：

可知只有当第一个串的头部和第一个串的尾部、第二个串的头部和第二个串的尾部、第一个串的头部和第二个串的尾部、第一个串的尾部和第二个串的头部四种情况才会使得回文的长度增长。因此，布尔型变量用表示串从到，从到能否组成新串，初始化为,则采取区间动态规划，每次更新最大值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const ll mod = 998244353;
char a[55], b[55];
bool dp[55][55][55][55];
int main()
{
    while (gets(a + 1) && gets(b + 1))
    {
        int len1 = strlen(a + 1);
        int len2 = strlen(b + 1);
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= len1 + 1; i++)
            for (int j = 1; j <= len2 + 1; j++)
                dp[i][i][j][j - 1] = dp[i][i - 1][j][j] = dp[i][i - 1][j][j - 1] = 1;
        int ans = 0;
        for (int l1 = 0; l1 <= len1; l1++)
            for (int l2 = 0; l2 <= len2; l2++)
                for (int i = 1, j = i + l1 - 1; j <= len1; i++, j++)
                    for (int k = 1, l = k + l2 - 1; l <= len2; k++, l++)
                    {
                        if (!dp[i][j][k][l])
                        {
                            bool b1 = i <= j && a[i] == a[j] && dp[i + 1][j - 1][k][l];
                            bool b2 = k <= l && b[k] == b[l] && dp[i][j][k + 1][l - 1];
                            bool b3 = l > 0 && a[i] == b[l] && dp[i + 1][j][k][l - 1];
                            bool b4 = j > 0 && a[j] == b[k] && dp[i][j - 1][k + 1][l];
                            dp[i][j][k][l] = b1 || b2 || b3 || b4;
                        }
                        if (dp[i][j][k][l])
                            ans = max(ans, l1 + l2);
                    }
        printf("%d\n", ans);
    }
    return 0;
}