COMPFEST 13 - Finals H. Holiday Wall Ornaments 题解

从动态规划的角度考虑，很容易想到的一种状态是当前位置前 $m$ 的字符的状态，但这样的状态数为 $2^m$ ，显然不可行。不妨进一步想，当前字符串能对后面产生影响的只有与字符串 $b$ 的前缀匹配的部分，所以状态可以被优化为当前字符串的后缀与 $b$ 的前缀最大匹配长度。整个 dp 的状态 $dp_{i, j, k}$ 为当前位置 $i$ , $b$ 作为子串已经出现了 $j$ 次，最长公共前后缀的长度为 $k$ 。

为了实现 $O(1)$ 转移，我们还需要预处理对于 $b$ 的所有后缀，在后面加 0 或者加 1 之后其后缀与 $b$ 的前缀的最大匹配状态。

代码 #

#include <bits/stdc++.h>
using namespace std;
const int N=500;
short dp[N+1][N+1][N+1], nxt[N+1][2];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    a=' '+a, b=' '+b;
    for (int i=0; i<=m; i++) {
        for (int x : {0, 1}) {
            string s=b.substr(1, i)+char('0'+x);
            for (int j=min(m, (int)size(s)); j>=1; j--) {
                if (b.substr(1, j) == s.substr(size(s)-j)) {
                    nxt[i][x]=j;
                    break;
                }
            }
        }
    }
    auto ckmin=[](auto& a, auto b) { if (b<a) a=b; };
    for (int i=0; i<=n; i++)
        for (int j=0; j<=n; j++)
            for (int k=0; k<=m; k++) dp[i][j][k]=20000;
    dp[0][0][0]=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<=n; j++)
            for (int k=0; k<=m; k++)
                for (int x : {0, 1})
                    ckmin(dp[i+1][j+(nxt[k][x]==m)][nxt[k][x]],
                          dp[i][j][k]+(a[i+1]!='0'+x));
    for (int i=0; i<=n-m+1; i++) {
        auto ans=*min_element(dp[n][i], dp[n][i]+m+1);
        cout << (ans==20000 ? -1 : ans) << " \n"[i==n-m+1];
    }
}