自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 22:32:54，当前版本为作者最后更新于2021-08-07 13:15:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先，感谢大家阅读！

思路：

本题字符串的内容只用 A 和 B，那么肯定与这两个字母有关。

我们可以设这个字符串为 $S$ ，长度为 $n$ ，要将 $S_0 - S_{n-1}$ 都变为 A，那么对于 $S_i$ 显然有 $2$ 种情况： $S_i='A'$ 和 $S_i='B'$ 。

这样我们就要分类讨论了。

1. 若 $S_i='A'$ ：那么将 $S_0-S_i$ 都变为 A 的操作总数显然为 $S_0-S_{i-1}$ 都变为 A 的操作总数（① $S_i='A'$ ，所以不用变）。将 $S_0-S_i$ 都变为 B 的操作总数显然就为将 $S_0-S_{i-1}$ 都变为 A 的操作总数 $+1$ （②把 $S_0-S_i$ 变成 B）和 $S_0-S_{i-1}$ 都变为 B 的操作总数 $+1$ （③把自己变成 B）的最小值。

2. 若 $S_i='B'$ ：那么和上文类似。将 $S_0-S_i$ 都变为 A 的操作总数显然为就为将 $S_0-S_{i-1}$ 都变为 B 的操作总数 $+1$ （④把 $S_0-S_i$ 变成 A）和 $S_0-S_{i-1}$ 都变为 A 的操作总数 $+1$ （⑤把自己变成 A）的最小值。将 $S_0-S_i$ 都变为 B 的操作总数显然就为 $S_0-S_{i-1}$ 都变为 B 的操作总数（⑥ $S_i='B'$ ，所以不用变）。

这么长的文字也许不太好理解，就具体用实现在说明一遍（针对 C++，尽量使其他语言可以理解）：

定义 $dpa_i$ 为将 $S_0-S_i$ 都变为 A 的操作总数。 $dpb_i$ 为将 $S_0-S_i$ 都变为 B 的操作总数。

若 $S_i='A'$ ： 则 $dpa_i=dpa_{i-1}$ （①）； $dpb_i=min(dpb_{i-1}+1,dpa_{i-1}+1)$ （②和③的最小值，min代表最小值）

若 $S_i='B'$ ： 则 $dpa_i=min(dpa_{i-1}+1,dpa_{i-1}+1)$ （④和⑤的最小值，min代表最小值）； $dpb_i=dpb_{i-1}$ （⑥）

枚举 $n$ 遍，就可以了。

• 记得给 $dpa_i$ 和 $dpb_i$ 赋初值。

• PS. $'A','B'$ 表示字符 A 和字符 B。

代码：

#include<iostream>
using namespace std;
int dpa[1000009],dpb[1000009],n;
char s[1000009];
int main(){
	cin>>n;
	cin>>s;
	dpa[0]=(s[0]=='B');//初值
	dpb[0]=(s[0]=='A');//初值
	for(int i=1;i<n;i++){
		if(s[i]=='A')dpa[i]=dpa[i-1],dpb[i]=min(dpa[i-1]+1,dpb[i-1]+1);
		else dpa[i]=min(dpa[i-1]+1,dpb[i-1]+1),dpb[i]=dpb[i-1];
	}
	cout<<dpa[n-1];//数组下标从0开始，所以要-1
}