题解：P11202 [JOIG 2024] 名前 / Name

· · 题解

前言

看了下题解区，全是 bfs 写法，所以专门搓了一篇 dp 来补一下。

思路

发现去掉 k 的限制（即 k=0 的时候），就是类似公共子序列的做法，但是有 k 的限制，这部分不太好处理。容易想到直接压进去前 k 位字母分别填了什么，这样是正确的，但是复杂度不允许，时空间 O(52^k\times nm) 易爆炸。

现在考虑哪些状态可以优化掉。由于 k 比较小，我们发现：如果需要向序列中补一些既不属于 s 又不属于 t 的字母（不如成为集合外的字母），那么我们并不用考虑集合外的字母之间的间隔问题（k 很小，全集比较大），也就是说：需要补一些集合外的字母的情况，只会在只考虑集合中的字母之间间隔过小时出现。
那么这 k 维可以由 52 个状态优化成 4 个状态：这一位的字母是 选择的字符串 S 中的字母 / 选择字符串 T 中的字母 / 两者当前位相同的字母（即两个串都选择） / 补的集合外的字母。我们可以由这些状态推出前 k 个字母中两个串各有几个，从而得出哪些字母不能选。
为了方便，可以直接使用 4 进制的状压，直接进行滚动即可。

最后再处理一下往当前结尾的状态里面塞集合外的字母的最小值即可，时空复杂 O(4^k\times nm)。

Code

Talk is cheap, show me the code.

// Problem: P11202 [JOIG 2024] 名前 / Name
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11202
// Memory Limit: 1 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace FastIO {
    char gc() {
        static char buf[1 << 24], *is = buf, *it = buf;
        if (is == it) is = buf, it = is + fread(buf, 1, 1 << 24, stdin);
        return is == it ? EOF : *is ++;
    }
    char out[1 << 24];
    int len;
    void flush() { fwrite(out, 1, len, stdout), len = 0; }
    void pc(char x) {if (len == 1 << 24) flush(); out[len ++] = x;}
    struct Flusher {~Flusher() {flush();} } Fls;
    // #define gc() getchar()
    // #define pc(X) putchar(X)
    inline void read(char& ch) {ch = gc();}
    inline void read(char *s) {
        char ch = gc();
        while (ch < 33 || ch > 126) ch = gc();
        for (; ch >= 33 && ch <= 126; ch = gc()) *s++ = ch;
        *s = '\0';
    }
    template <class T>
    inline void read(T &x) {
        char c, flag = 0;
        while ((c = gc()) < '0' || c > '9') flag |= c == '-';
        x = c & 15;
        while ((c = gc()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c & 15);
        if (flag) x = ~x + 1;
    }
    template <class T, class ...T1>
    inline void read(T &x, T1 &...x1) {read(x), read(x1...);}
    template <class T>
    inline void _put(T x) {if(x > 9) _put(x / 10); pc((x % 10) | 48);}
    template <class T>
    inline void write(T x) {if(x < 0) pc('-'), x = ~x + 1; _put(x);}
    template <> inline void write(char x) {pc(x);}
    template <class T, class ...T1>
    inline void write(T x, T1 ...x1) {write(x), write(x1...);}
}
using FastIO::read;
using FastIO::write;
template <class T>
inline bool chkmin(T &x, T y) {return x > y ? x = y, 1 : 0;}
template <class T>
inline bool chkmax(T &x, T y) {return x < y ? x = y, 1 : 0;}

const int N = 5e2 + 10, M = 1 << 6;
int n, m, k, dp[N][N][M], ans, lim;
char s[N], t[N];
bool check(int i, int j, int sta, int f1, int f2) {
    int cs = 0, ct = 0, flag = 0;
    while(sta) cs += sta & 3 & 1, ct += (sta & 3 & 2) >> 1, sta >>= 2;
    if(f1) for(int p = 1; p <= cs && p < i; ++p) flag |= (s[i] == s[i - p]);
    if(f1) for(int p = 1; p <= ct && j - p - f2 + 1 > 0; ++p)
        flag |= (s[i] == t[j - p - f2 + 1]);
    if(f2) for(int p = 1; p <= ct && p < j; ++p) flag |= (t[j] == t[j - p]);
    if(f2) for(int p = 1; p <= cs && i - p - f1 + 1 > 0; ++p)
        flag |= (t[j] == s[i - p - f1 + 1]);
    return !flag;
}
void solve(int i, int j, int f1, int f2) {
    int now = f1 * 1 + f2 * 2;
    for(int sta = 0; sta <= lim; ++sta) if(check(i, j, sta, f1, f2))
        chkmin(dp[i][j][((sta << 2) + now) & lim], dp[i - f1][j - f2][sta] + 1);
    for(int sta = lim; ~sta; --sta) for(int p = 1; p <= k; ++p)
        chkmin(dp[i][j][(sta << (p * 2)) & lim], dp[i][j][sta] + p);
}

signed main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    read(n, m, k), read(s + 1), read(t + 1); memset(dp, 0x3f, sizeof dp);
    dp[0][0][0] = 0, ans = (n + m) * (k + 1), lim = (1 << (2 * k)) - 1;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j) {
            if(i && j && s[i] == t[j]) solve(i, j, 1, 1);
            if(i) solve(i, j, 1, 0);
            if(j) solve(i, j, 0, 1);
        }
    for(int sta = 0; sta <= lim; ++sta) chkmin(ans, dp[n][m][sta]);
    write(ans);
    return 0;
}

End

如有问题，欢迎指正。