[DTCPC 2024] 戈布

· · 题解

类似的题在 CF 好像叫做 Balanced String 来着。01 序列任意交换都要典成土了。

首先考虑一个 01 序列 s 通过任意交换变成 t 的最小次数是多少。显然我们一次可以将一对 s 中的子序列 01 与 t 中对应位置的一个 10（或相反，s 中的 10 与 t 中的 01）交换，这样一下子减少了 2 个不同的位置。所以最小次数是 \dfrac12\operatorname{popcount}(s\operatorname{xor} t)。

问题转换为，找一个 01 序列满足题目的条件，并且与 s 不同的位置最少。

直接考虑 dp。f_{i,j,k,0/1} 表示前 i 位，填了 j 个 1，最后一个极长 1 连续段长为 k，第 i 位填的 0/1 的最少不同位置数。

则有转移：

\begin{aligned} f_{i,j,k,0}&=[s_{i}\neq 0]+\min(f_{i-1,j,k,0},f_{i-1,j,k,1})+\\ f_{i,j,k,1}&=\left(\sum_{p=i-k+1}^i [s_i\neq1]\right)+\min_{l=0}^{k-1}f_{i-k,j-k,l,0} \end{aligned}

第一个式子 \Theta(1) 转移，第二个式子前面一项前缀和即可，后面一项维护 dp 数组前缀 \min 即可。

然后可以对第三维滚动数组。空间降为 \Theta(n^2)。

时间复杂度 \Theta(n^3)。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 810;

int n, m, ans;
char s[maxn];
int t[maxn];
int f[maxn][maxn][2];
int tmpf[maxn][maxn][2];
int g[maxn][maxn];
int tmpg[maxn][maxn];

signed main() {
    cin >> s + 1, n = strlen(s + 1);
    for (int i = 1; i <= n; i++) m += s[i] - '0', t[i] = t[i - 1] + s[i] - '0';
    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));
    memset(tmpf, 0x3f, sizeof(tmpf));
    memset(tmpg, 0x3f, sizeof(tmpg));
    ans = f[0][0][0];
    f[0][0][0] = 0;
    g[0][0] = 0;
    for (int k = 0; k <= m; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j][0] = min(f[i - 1][j][0], f[i - 1][j][1]) + (s[i] == '1');
                if (k && k <= i && k <= j) f[i][j][1] = tmpg[i - k][j - k] + k - t[i] + t[i - k];
                if (k) g[i][j] = tmpg[i][j];
                g[i][j] = min(g[i][j], f[i][j][0]);
            }
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                tmpf[i][j][0] = f[i][j][0];
                tmpf[i][j][1] = f[i][j][1];
                tmpg[i][j] = g[i][j];
            }
        }
        ans = min(ans, f[n][m][0]);
        ans = min(ans, f[n][m][1]);
    }
    cout << ans / 2 << endl;
    return 0;
}