【NOIP模拟赛】DNA序列

2014年4月5日1,2320

题目描述

来自JSSI(Jinkela State Scientific Institute)的科学家们尝试制造一个长度为N并且只包含A的DNA序列,不出意外地失败了。他们得到了一个含有A和B两种部件的序列。现在他们打算对实验结果进行篡改,来得到一个全部是A的序列。篡改的方式有两种:

1 更改某一位上部件的状态(A变成B,B变成A)

2 更改某个前缀内所有部件的状态

两种操作的代价都为1。

你的任务自然是求最小代价。

输入

第一行为N,序列长度。

第二行是一个长度为N且只包含A和B的字符串,表示初始序列。

输出

最小代价。

样例输入

0

样例输出

4

数据范围

对于10%的数据,N<=10

对于70%的数据,N<=100000

对于100%的数据,N<=1000000

题解

直接dp或者倒过来贪心都行