自动搬运

查看原文

来自洛谷，原作者为

	TernaryTree ?steal a life

搬运于2025-08-24 22:55:19，当前版本为作者最后更新于2024-02-17 18:00:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

类似的题在 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;
}