前言

这对一个小白来说。。区间dp会一点不过，还是很难很难去递推出这个状态转移方程。。
通过观摩各个大佬的题解，勉勉强强懂了一点点 +_+ 写的不咋地的话，希望大佬们轻点喷呀！

题目描述

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

解题思路

向放下区间dp的板子把

for(int len = 1;len<=n;len++){//枚举长度
    for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
        int ends = j+len - 1;
        for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
            dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
        }
    }
}

参考题解
那么我们开一个四维的动规数组 dp[i][j][k][z] 表示a[i……j]与b[k……z]能不能构成回文串。
那么当(j-i)+(z-k)小于等于1的时候这个dp初值就为1*
后序的状态转移方程，真的看了很久 = =，感谢邓老师和其他大佬们的题解！！

//回文串最左边的字符a[i]和最右边的字符a[j]相等
dp[i][j][k][z] |= dp[i+1][j-1][k][z];
//回文串最左边的字符b[k]和最右边的字符b[z]相等
dp[i][j][k][z] |= dp[i][j][k+1][z-1];
//回文串最左边的字符a[i]和最右边的字符b[z]相等
dp[i][j][k][z] |= dp[i+1][j][k][z-1];
//回文串最左边的字符b[k]和最右边的字符a[j]相等
dp[i][j][k][z] |= dp[i][j-1][k+1][z];

最后如果这一个i,j,k,z组合构成了回文串，把长度更新。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43627915&returnHomeType=1&uid=919749006

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 55;
int dp[N][N][N][N];
int main() {
    js;
    int T;
    cin >> T;
    while (T--) {
        string a, b;
        cin >> a >> b;
        int ans = 0;
        int lena = a.size(), lenb = b.size();
        for (int l1 = 0; l1 <= lena; l1++) {
            for (int l2 = 0; l2 <= lenb; l2++) {
                for (int i = 1, j = l1; j <= lena; i++, j++) {
                    for (int k = 1, z = l2; z <= lenb; k++, z++) {
                        if (l1 + l2 <= 1)
                            dp[i][j][k][z] = 1;
                        else {
                            dp[i][j][k][z] = 0;
                            if (a[i - 1] == a[j - 1] && l1 > 1)
                                dp[i][j][k][z] |= dp[i + 1][j - 1][k][z];
                            if (b[k - 1] == b[z - 1] && l2 > 1)
                                dp[i][j][k][z] |= dp[i][j][k + 1][z - 1];
                            if (a[i - 1] == b[z - 1] && l1 && l2)
                                dp[i][j][k][z] |= dp[i + 1][j][k][z - 1];
                            if (a[j - 1] == b[k - 1] && l1 && l2)
                                dp[i][j][k][z] |= dp[i][j - 1][k + 1][z];
                        }
                        if (dp[i][j][k][z])
                            ans = max(ans, l1 + l2);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return  0;
}