D. Balanced String
You are given a binary string $s$ (a binary string is a string consisting of characters 0 and/or 1).
Let's call a binary string balanced if the number of subsequences 01 (the number of indices $i$ and $j$ such that $1 \le i < j \le n$, $s_i=0$ and $s_j=1$) equals to the number of subsequences 10 (the number of indices $k$ and $l$ such that $1 \le k < l \le n$, $s_k=1$ and $s_l=0$) in it.
For example, the string 1000110 is balanced, because both the number of subsequences 01 and the number of subsequences 10 are equal to $6$. On the other hand, 11010 is not balanced, because the number of subsequences 01 is $1$, but the number of subsequences 10 is $5$.
You can perform the following operation any number of times: choose two characters in $s$ and swap them. Your task is to calculate the minimum number of operations to make the string $s$ balanced.
Input
The only line contains the string $s$ ($3 \le |s| \le 100$) consisting of characters 0 and/or 1.
Additional constraint on the input: the string $s$ can be made balanced.
Output
Print a single integer — the minimum number of swap operations to make the string $s$ balanced.
Examples
input
101
output
0
input
1000110
output
0
input
11010
output
1
input
11001100
output
2
Note
In the first example, the string is already balanced, the number of both 01 and 10 is equal to $1$.
In the second example, the string is already balanced, the number of both 01 and 10 is equal to $6$.
In the third example, one of the possible answers is the following one: 11010 $\rightarrow$ 01110. After that, the number of both 01 and 10 is equal to $3$.
In the fourth example, one of the possible answers is the following one: 11001100 $\rightarrow$ 11001010 $\rightarrow$ 11000011. After that, the number of both 01 and 10 is equal to $8$.
解题思路
这题最关键的地方是要发现不管怎么交换字符，字符串中$01$和$10$的总数总是不变。
首先字符串中大小为$2$的子序列无非就只有如下$4$种：$00$、$11$、$01$、$10$。可以发现无论我们怎么交换，字符串中$0$和$1$的数量总是不变，因此$00$和$11$的总和也总是不变。假设字符串中$0$的数量为$s_0$，$1$的数量为$s_1$，那么$\dfrac{s_0(s_0-1)}{2} + \dfrac{s_1(s_1-1)}{2}$就是定值，也意味着$01$和$10$的数量也总是不变，因为$m = \dfrac{n(n-1)}{2}-\left(\dfrac{s_0(s_0-1)}{2} + \dfrac{s_1(s_1-1)}{2}\right)$也是一个定值。由于题目保证一定可以得到平衡字符串，因此$m$必然是偶数，意味着我们要通过最小的交换次数使得字符串中$01$和$10$的数量都等于$\frac{m}{2}$。
问题可以等价成求最小的交换次数使得字符串中子序列$01$的数量恰好为$\frac{m}{2}$。可以发现交换相同字符是没有意义的，因此我们每次都应该交换$0$和$1$，相应的就会有两个不同位置的字符发生改变。为了方便我们把每一次的交换都记到$0$变$1$的位置，也就是说如果要把某个位置的$0$变$1$，那么交换的次数就加$1$，而$1$变$0$的位置就不再统计（保证$0 \to 1$，$1 \to 0$出现的次数相同）。
因此可以定义状态$f(i,c_0,j)$表示交换后前$i$个字符中有$c_0$个$0$且$10$的数量为$j$的所有方案中，交换次数的最小值。根据第$i$个字符是$0$还是$1$进行状态划分。如果$s_i$本身就是$0$，那么就有状态转移方程
$$f(i, c_0, j) = \min \begin{cases}
f(i-1, c_0-1, j), \quad &s_i \to 0 \\
f(i-1, c_0, j - c_0) + 1, \quad &s_i \to 1
\end{cases}$$
如果$s_i$本身就是$1$，那么就有状态转移方程
$$f(i, c_0, j) = \min \begin{cases}
f(i-1, c_0, j - c_0), \quad &s_i \to 1 \\
f(i-1, c_0 - 1, j), \quad &s_i \to 0
\end{cases}$$
综合一下就有$$f(i,c_0,j) = \min\left\{ f(i-1,c_0-1,j), \, f(i-1,c_0,j-c_0)+\left[ s_i \mathrm{==} 0 \right] \right\}$$
最后答案就是$f(n,s_0,m)$。
AC代码如下，时间复杂度为$O(n^4)$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5
6 const int N = 110, M = N * N / 4;
7
8 char s[N];
9 int f[N][N][M];
10
11 int main() {
12 scanf("%s", s + 1);
13 int n = strlen(s + 1);
14 int s0 = 0, s1 = 0;
15 for (int i = 1; i <= n; i++) {
16 if (s[i] & 1) s1++;
17 else s0++;
18 }
19 int m = n * (n - 1) / 2 - s0 * (s0 - 1) / 2 - s1 * (s1 - 1) / 2 >> 1;
20 memset(f, 0x3f, sizeof(f));
21 f[0][0][0] = 0;
22 for (int i = 1; i <= n; i++) {
23 for (int j = 0; j <= min(i, s0); j++) {
24 for (int k = 0; k <= m; k++) {
25 if (j) f[i][j][k] = f[i - 1][j - 1][k];
26 if (k >= j) f[i][j][k] = min(f[i][j][k], f[i - 1][j][k - j] + (s[i] + 1) % 2);
27 }
28 }
29 }
30 printf("%d\n", f[n][s0][m]);
31
32 return 0;
33 }
参考资料
Educational Codeforces Round 153 Editorial：https://codeforces.com/blog/entry/119504
Educational Codeforces Round 153 (Rated for Div. 2) 详细题解（A~D）：https://zhuanlan.zhihu.com/p/650743034
标签：10,01,String,int,number,balanced,Balanced,string From： https://www.cnblogs.com/onlyblues/p/17680838.html