题解

wangbinfeng · 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} （①）；

若 $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
  }