问题 25629 --翻转奶牛

25629: 翻转奶牛

时间限制: 1 Sec  内存限制: 128 MB
提交: 86  解决: 29
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][112kb]

题目描述

农夫约翰把N (1 N 5000)头奶牛排成了一行,其中大部分的奶牛都很好,他们的脸都朝向正面,但就有一小撮的奶牛是朝向背面的,为了追求完美,约翰决定要让所有的牛都朝向正面。

    幸运的是,约翰最近刚买了一部自动翻牛机。不过因为他买的是打折机型,所以事先必须要设定单次翻转的牛头数K (1 K N),一旦固定,就再也不能修改了。而且这台机器只能同时翻转站在一起的奶牛,每次使用的时候,它会翻转相邻的K头奶牛(不能少于K头,就算靠在队列的两个端点上也一样),一头牛在被翻转之前是朝向正面的,使用之后就会被翻到背面去了,反之亦然。

    由于约翰只能选一个不可以修改的K,所以请帮他确定一个K,使得使用机器的次数最少,同时,也请把这个最少的次数M求出来(如果有多个K满足条件,输出最小的那个)。

输入

第一行:单个整数:N

第二行到第N + 1行:第i + 1行只有一个字符 B F,表示第i头奶牛是朝向正面(F)还是背面的(B)。

输出

第一行:两个用空格分开的整数:KM

样例输入

7 
B 
B 
F 
B 
F 
B 
B

样例输出

3 3

提示

(选择K = 3,翻转三次:(1,2,3)(3,4,5)(5,6,7)即可)

来源

[提交][状态]