← 返回题目列表

Codeforces · 771/D

D. 熊公司

中文机器翻译题面 查看原题

Bear Limak 为编程竞赛准备问题。当然,在声明中提及赞助商名称是不专业的。利马克认真对待此事,他将更改一些措辞。为了使其仍然可以阅读,他会尽量少地修改每个单词。

Limak 有一个由大写英文字母组成的字符串 s。他一步就能交换字符串中两个相邻的字母。例如,他可以一步将字符串“ABBC”转换为“BABC”或“ABCB”。

Limak 想要获取一个不包含子字符串“VK”的字符串(即不应有紧随字母“K”的字母“V”)。可以很容易地证明,对于任何初始字符串 s 都是可能的。

Limak 最少可以移动多少步?

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 75) - 字符串的长度。

第二行包含字符串s,由大写英文字母组成。字符串的长度等于n。

输出

打印一个整数,表示 Limak 可以执行的最小可能移动次数,以获得不带子字符串“VK”的字符串。

示例

输入 #1

4
VKVK

输出 #1

3

输入 #2

5
BVVKV

输出 #2

2

输入 #3

7
VVKEVKK

输出 #3

3

输入#4

20
VKVKVVVKVOVKVQKKKVVK

输出#4

8

输入 #5

5
LIMAK

输出 #5

0

注意

在第一个示例中,初始字符串是“VKVK”。最小可能的移动次数为 3。一种最佳的移动顺序是:

1. 交换最后两个字母。该字符串变为“VKKV”。
2. 交换前两个字母。该字符串变为“KVKV”。
3. 交换第二个和第三个字母。该字符串变为“KKVV”。事实上,这个字符串没有子字符串“VK”。

在第二个示例中,有两个最佳的移动序列。一是“BVVKV”→“VBVKV”→“VVBKV”。另一种是“BVVKV”→“BVKVV”→“BKVVV”。

在第五个示例中,不需要交换。