【题解】NC13230 区间DP

608 浏览 0 回复 2020-03-25

expect2004

+关注

设 $dp[i][j][k][l]$ 代表字符串 $\texttt{A}$ 中 $i$ 至 $j$ 个字符，字符串 $\texttt{B}$ 中 $k$ 至 $l$ 个字符是否能构成回文串。

然后区间DP套路转移。

时间复杂度 $O(T|a|^2|b|^2)$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 50 + 7;
char s[maxn], p[maxn];
int dp[maxn][maxn][maxn][maxn], T;
int main() {
    cin >> T;
    while (T--) {
        cin >> (s + 1) >> (p + 1);
        int n = strlen(s + 1), m = strlen(p + 1);
        int ans = 0;
        for (int sl = 0; sl <= n; ++sl) {
            for (int pl = 0; pl <= m; ++pl) {
                for (int i = 1; i + sl - 1 <= n; ++i) {
                    for (int k = 1; k + pl - 1 <= m; ++k) {
                        int j = i + sl - 1, l = k + pl - 1;
                        if (sl + pl <= 1)
                            dp[i][j][k][l] = 1;
                        else {
                            dp[i][j][k][l] = 0;
                            if (s[i] == s[j] && sl)
                                dp[i][j][k][l] |= dp[i + 1][j - 1][k][l];
                            if (p[k] == p[l] && pl)
                                dp[i][j][k][l] |= dp[i][j][k + 1][l - 1];
                            if (s[i] == p[l] && sl && pl)
                                dp[i][j][k][l] |= dp[i + 1][j][k][l - 1];
                            if (p[k] == s[j] && sl && pl)
                                dp[i][j][k][l] |= dp[i][j - 1][k + 1][l];
                        }
                        if (dp[i][j][k][l])
                            ans = max(ans, sl + pl);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}