问题1696--牛客网-白菜的基因序列

1696: 牛客网-白菜的基因序列

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

大科学家d最近在研究转基因白菜，白菜的基因序列由一串大写英文字母构成，d经过严谨的推理证明发现，只有当白菜的基因序列呈按位非递减形式时，这株白菜的高附加值将达到最高，于是优秀的d开始着手修改白菜的基因序列，d每次修改基因序列的任意位需要的代价是1，d想知道，修改白菜的基因序列使其高附加值达到最高，所需要的最小代价的是多少。

输入

第一行一个正整数n(1≤n≤1000000)
第二行一个长度为n的字符串，表示所给白菜的基因序列
保证给出字符串中有且仅有大写英文字母

输出 

输出一行，表示最小代价

样例输入 Copy 

5
ACEBF

样例输出 Copy 

1

提示

样例解释： 
改成ACEEF或者ACEFF，都只用改动一个字符，所需代价最小为1
更多样例：
13
CCCDDDAAAAAAA

输出为6

来源/分类

27初级算法-经典动态规划 
[提交] [状态]