一、题意理解

我们有两个字符串 $a$ 和 $b$，长度分别为 $|a|$ 和 $|b|$。

我们要构造一个字符串 $c$，长度为 $|a| + |b|$，并且 $c$ 可以拆成两个不相交的子序列，一个等于 $a$，一个等于 $b$。

换句话说，$c$ 是 $a$ 和 $b$ 的 交错（interleaving），保持 $a$ 和 $b$ 各自的字符顺序。

然后定义 $c$ 的价值 = 最长回文子串的长度。

我们要在所有可能的 $c$ 中，找到最大的价值，并输出它。

---

二、初步观察

• 因为 $c$ 是 $a$ 和 $b$ 的交错，所以 $c$ 的字符集是 $a$ 和 $b$ 的字符集的并。
• 最长回文子串可能完全来自 $a$，完全来自 $b$，或者跨越 $a$ 和 $b$ 的字符。
• 如果最长回文子串完全在 $a$ 中，那么它的长度就是 $a$ 的最长回文子串长度，与 $b$ 无关；同理 $b$。
• 如果回文子串同时包含 $a$ 和 $b$ 的字符，那么我们必须能在 $c$ 中安排这些字符，使得它们形成一个回文，并且保持 $a$ 和 $b$ 各自的顺序。

---

三、关键思路

设 $dp[i][j][x][y]$ 表示考虑 $a$ 的子串 $a[i..j]$ 和 $b$ 的子串 $b[x..y]$ 时，它们能形成的回文串的最大长度。

但这样状态太多：$O(n^2 m^2)$ 太大（$n, m \le 50$ 时还行？$T=50$，但 $a,b$ 长度没说，假设 $\le 50$ 的话，$50^4 = 6.25\times 10^6$ 勉强可做）。

实际上更常见的做法是：

枚举回文串的中心（或中心区间），然后向两边扩展，同时从 $a$ 和 $b$ 中取字符，但要保持 $a$ 和 $b$ 的顺序。

---

我们可以用区间 DP：

设 $f[l][r][p][q]$ 表示用 $a[l..r]$ 和 $b[p..q]$ 这些字符（按顺序交错）能构成的最长回文子串长度。

转移：

• 如果 $a[l] = a[r]$ 且 $l < r$，那么可以用它们作为回文的两端，然后 $f[l][r][p][q] = 2 + f[l+1][r-1][p][q]$。
• 如果 $a[l] = b[q]$ 且 $q \ge p$，那么 $f[l][r][p][q] = 2 + f[l+1][r][p][q-1]$。
• 如果 $b[p] = a[r]$ 且 $r \ge l$，那么 $f[l][r][p][q] = 2 + f[l][r-1][p+1][q]$。
• 如果 $b[p] = b[q]$ 且 $p < q$，那么 $f[l][r][p][q] = 2 + f[l][r][p+1][q-1]$。
• 还有长度为 1 或 2 的回文情况。

但这样状态是 $O(n^2 m^2)$，在 $n,m \le 50$ 时是 $50^4 = 6.25\times 10^6$，转移 $O(1)$，可以接受。

---

四、状态设计简化

更常见的做法是设 $dp[i][j][k][l]$ 表示 $a[i..j]$ 和 $b[k..l]$ 能组成的最大回文长度。

初始化：

• 空串：0
• 单个字符（来自 $a$ 或 $b$）：1

转移：

1. $dp[i][j][k][l] = \max(dp[i+1][j][k][l], dp[i][j-1][k][l], dp[i][j][k+1][l], dp[i][j][k][l-1])$（舍弃一端）
2. 如果 $a[i] = a[j]$ 且 $i < j$，则 $dp[i][j][k][l] = \max(dp[i][j][k][l], 2 + dp[i+1][j-1][k][l])$
3. 如果 $b[k] = b[l]$ 且 $k < l$，则 $dp[i][j][k][l] = \max(dp[i][j][k][l], 2 + dp[i][j][k+1][l-1])$
4. 如果 $a[i] = b[l]$，则 $dp[i][j][k][l] = \max(dp[i][j][k][l], 2 + dp[i+1][j][k][l-1])$
5. 如果 $b[k] = a[j]$，则 $dp[i][j][k][l] = \max(dp[i][j][k][l], 2 + dp[i][j-1][k+1][l])$
6. 如果 $a[i] = b[k]$ 且 $i \le j$ 且 $k \le l$，这种情况其实包含在上面？不，这是两端分别来自 $a$ 和 $b$ 的开头，但必须 $i$ 和 $k$ 是各自第一个字符？其实我们枚举的是子串，所以这种情况就是 $a[i]$ 和 $b[k]$ 作两端，但 $i$ 和 $k$ 是各自子串的第一个字符，$j$ 和 $l$ 是最后一个字符，所以这种情况就是 $a[i]=b[k]$ 时，$2 + dp[i+1][j][k+1][l]$，但要求 $i \le j$ 且 $k \le l$。

实际上，为了编码方便，我们可以把 $a$ 和 $b$ 连接成一个字符串 $s$ 长度 $n+m$，然后用区间 DP $g[l][r]$ 表示 $s[l..r]$ 作为 $c$ 的子串时，能否由 $a$ 和 $b$ 的子序列组成，并且是回文。但这样要记录 $a$ 和 $b$ 的选取情况，状态要加维度。

---

五、标准解法思路

已知这类题的常见解法：

设 $f[i][j][k][l]$ 表示 $a[i..j]$ 和 $b[k..l]$ 能形成的最大回文子串长度。

初始化：任何长度为 1 的子串（来自 $a$ 或 $b$）回文长度为 1。

转移：

• 从 $a$ 取两端：若 $a[i] = a[j]$ 且 $i \le j$，则 $f[i][j][k][l] = \max(f[i][j][k][l], f[i+1][j-1][k][l] + 2)$
• 从 $b$ 取两端：若 $b[k] = b[l]$ 且 $k \le l$，则 $f[i][j][k][l] = \max(f[i][j][k][l], f[i][j][k+1][l-1] + 2)$
• 从 $a$ 取左，$b$ 取右：若 $a[i] = b[l]$，则 $f[i][j][k][l] = \max(f[i][j][k][l], f[i+1][j][k][l-1] + 2)$
• 从 $b$ 取左，$a$ 取右：若 $b[k] = a[j]$，则 $f[i][j][k][l] = \max(f[i][j][k][l], f[i][j-1][k+1][l] + 2)$

同时，还可以舍弃一端： $f[i][j][k][l] = \max(f[i+1][j][k][l], f[i][j-1][k][l], f[i][j][k+1][l], f[i][j][k][l-1])$

答案就是 $f[0][n-1][0][m-1]$，其中 $n = |a|, m = |b|$。

---

六、样例验证

样例1：

a = "aa", b = "bb"

最大回文：可以构成 "abba" 作为 $c$ 的子串，长度 4。

样例2：

a = "a", b = "aaaabcaa"

最大回文：可以构成 "aaa" 或 "abcba" 等，最长是 5。

---

七、算法复杂度

状态数 $O(n^2 m^2)$，$n,m \le 50$ 时 $2500 \times 2500 = 6.25\times 10^6$，转移 $O(1)$，可过。

---

八、代码实现（C++）

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

const int N = 55;

int f[N][N][N][N];
char a[N], b[N];

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> (a + 1) >> (b + 1);
        int n = strlen(a + 1);
        int m = strlen(b + 1);
        
        memset(f, 0, sizeof f);
        
        for (int len1 = 0; len1 <= n; len1++)
            for (int len2 = 0; len2 <= m; len2++)
                for (int i = 1; i + len1 - 1 <= n; i++)
                    for (int k = 1; k + len2 - 1 <= m; k++) {
                        int j = i + len1 - 1;
                        int l = k + len2 - 1;
                        int &res = f[i][j][k][l];
                        if (len1 + len2 <= 1) {
                            res = len1 + len2;
                            continue;
                        }
                        
                        // 舍弃一个字符
                        if (len1 > 0) {
                            res = max(res, f[i+1][j][k][l]);
                            res = max(res, f[i][j-1][k][l]);
                        }
                        if (len2 > 0) {
                            res = max(res, f[i][j][k+1][l]);
                            res = max(res, f[i][j][k][l-1]);
                        }
                        
                        // 两端都选，且匹配
                        if (len1 > 1 && a[i] == a[j])
                            res = max(res, f[i+1][j-1][k][l] + 2);
                        if (len2 > 1 && b[k] == b[l])
                            res = max(res, f[i][j][k+1][l-1] + 2);
                        if (len1 > 0 && len2 > 0) {
                            if (a[i] == b[l])
                                res = max(res, f[i+1][j][k][l-1] + 2);
                            if (b[k] == a[j])
                                res = max(res, f[i][j-1][k+1][l] + 2);
                        }
                    }
        
        cout << f[1][n][1][m] << endl;
    }
    return 0;
}

---