P2882 [USACO07MAR] Face The Right Way G

题目描述

Farmer John 将他的 $N$（$1 \le N \le 5\,000$）头奶牛排成一排，其中许多奶牛面朝前，像好奶牛一样。不过，也有一些奶牛面朝后，他需要所有奶牛都面朝前，才能让生活完美。

幸运的是，FJ 最近买了一台自动奶牛翻转机。由于他购买的是折扣型号，该机器必须事先固定设置为一次性翻转连续的 $K$（$1 \le K \le N$）头奶牛，并且只能翻转排中连续相邻的一群奶牛。每次使用机器时，它会将一排中连续 $K$ 头奶牛的面朝方向全部反转（不能用于少于 $K$ 头奶牛，例如在奶牛队列的两端）。每头奶牛仍保持在原来的位置，但最终会面朝相反方向。原本面朝前的奶牛会被翻转为面朝后，反之亦然。

由于 FJ 必须选择一个固定不变的 $K$ 值，请帮助他确定能使所需操作次数达到最小的 $K$ 的最小值，并求出在该 $K$ 下所需的最少操作次数 $M$。

输入格式

第一行：一个整数 $N$。

第 $2$ 到第 $N+1$ 行：第 $i+1$ 行包含一个字符，F 或 B，表示第 $i$ 头奶牛是面朝前还是面朝后。

输出格式

第一行：两个空格分隔的整数 $K$ 和 $M$。

输入输出样例 #1

输入 #1

7
B
B
F
B
F
B
B

输出 #1

3 3

说明/提示

对于 $K = 3$，机器必须操作三次：翻转奶牛 $(1,2,3)$，然后翻转 $(3,4,5)$，最后翻转 $(5,6,7)$。

对于 $100\%$ 的数据，$1 \le N \le 5000$。

翻译由 DeepSeek V4 Pro 完成