#B. DNA

    传统题 1000ms 256MiB

DNA

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

生物学家希蒙发现了一种奇怪的DNA分子,最好描述为由N个字符组成的序列,字符取自集合{A, B}(只由AB组成)。一个不太可能的变异序列导致了一个只包含A的DNA链。生物学家们觉得这非常奇怪,于是开始更详细地研究这些突变。

他们发现了两种类型的突变。一种类型导致改变序列中的单个字符(A → B 或 B → A)。第二种类型改变了整个序列的前缀,具体地说是用另一个字符(A换成B,B换成A)替换位置从1到K的所有字符(对于某个介于1和N之间的K,包括K)。

计算将起始分子转换为其最终状态(仅包含A字符)所需的最少突变次数。突变可以以任何顺序发生。

输入格式

第一行一个整数,表示 NN

第二行 NN 个字符,表示该序列。

输出格式

一行,一个整数,表示答案。

样例 #1

样例输入 #1

4
ABBA

样例输出 #1

2

样例 #2

样例输入 #2

5
BBABB

样例输出 #2

2

样例 #3

样例输入 #3

12
AAABBBAAABBB

样例输出 #3

4

提示

1N1061\le N\le 10^{6}

序列仅由 'A','B' 构成。

【CQMC】重庆小码王C++月赛 - 算法组(进阶练习) #2

未参加
状态
已结束
规则
IOI
题目
3
开始于
2023-12-29 13:00
结束于
2024-1-4 0:00
持续时间
131 小时
主持人
参赛人数
22