老农民有N头牛， 每头牛或者朝前或者朝后。 为了让所有的牛都朝前， 买了一台自动转向机（真是蛋疼）， 这台机器需要人为的设置一个值K， 这样没操作一次， 恰好使得K头连续的牛转向。 求出为了让所有的牛都能面向前方需要的最少的操作次数M， 并进而确定与之对应的K值。
限制条件： 1<= N <= 5000
Sample input(F表示面向前方， B表示面向后方)：
N = 7BBFBFBB输出：K = 3M = 3即先反转1到3号牛， 然后在反转3到5号， 最后反转5号到7号。 步骤如下：
BBF BFBB ———-> FFB BFBB ———> FF FFB BB —–> FFFF FFF
我们看出， 对一个区间（大小为K， 当然连续）反转两次以上是多余的， 也就是说需要反转， 一次就够， 在反， 就等于没反了。
于是问题就变成了求解需要被反转的区间的集合。 我们首先考虑最左端的牛， 包含这头牛的区间只有一个， 即[0, K – 1]， 如果这头牛面超前，
就不需要反转， 否则， 这头牛面朝后， 当然这个区间（即[0, K – 1]）需要被反转了。这样问题的规模就变为n – 1， 不断的重复下去， 即可以求
出反转的次数了。
忽略掉每个区间重复反转的多与操作，只要存在所有牛面朝前的办法， 那么操作就和顺序无关了， 因为每个区间只反转一次或者不反转。
算法复杂度如何呢？
对所有的K（K 从1 到N）遍历搜索一次， 最坏情况下， 需要进行 N – K + 1次的反转（最后K- 1个无法反转， 要考虑可行性， 因为每次
必须要转K头牛， 而不能少于K头牛）， 每次反转需要操作K头牛， 所以总的复杂度为O（N^3）。
但是其实我们并不需要每次非要操作K头牛真的反转， 我们可以通过记录下每个区间是否反转了这一信息， 避免去做每一次的K头牛反转这一工作。 这样我们可以把时间复杂度降为O（N^2）。
具体的， 记录 f[i] = 区间[i, i + K – 1]是否进行了反转， 若反转了 f[i] = 1, 没有反转则记录 f[i] = 0， 这样我们考虑第i 头牛时(方向dir[i]， 记为0的时候， 表示朝前， 为1 表示朝后)， 如果 ∑f[j]， 从 i – K + 1 累加到 i- 1, 若这个sum 为奇数， 表明i头牛已经进行了奇数次的反转， 也就是说， 此时这头牛的方向和其最开始的方向相反， 同理， 若这个sum为偶数， 表明这头牛已经进行了偶数次的反转， 也就是此时这头牛的方向dir[i]和其最开始的方向相同。
我们有如下的观察：
∑ f[j] = ∑f[j] + f[i] – f[i – K + 1]
注意，， 第一个的求和 从 (i + 1) – K + 1 到 i
第二个求和从 i – K + 1 到 i – 1
有个上述公式， 我们就可以每一次在常数时计算上述的sum了。
另外我们有如下的观察：
dir[i] + sum <———> 0 + 奇数， 为奇数， 表示还需要反转一次（原方向就是朝前的了， 已经进行奇数次反转， 变成了朝后）
dir[i] + sum <———> 0 + 偶数， 为偶数， 表示不用反转了
dir[i] + sum <———> 1 + 奇数， 为偶数， 表示不需要反转了， 原方向为1， 奇数次后为超前（即0）
dir[i] + sum <———> 0 + 奇数， 为奇数， 表示还需要反转一次， 原方向为0， 已经朝前了。
综上， 我们总结， 当dir[i] + sum 为奇数的时候， 就需要反转， 为偶数时， 就不需要反转了。
总的程序如下：
#include <iostream>#include <cstring> // for memset#include <cstdio>using namespace std;const int MAX_N = 5000 + 10;int N;int dir[MAX_N];int f[MAX_N];int calc(int K) { // 反转区间大小memset(f, 0, sizeof(f));int res = 0; // 记录反转次数int sum = 0; // f[i]记录区间大小为K， 从i开始的和for(int i = 0; i + K <= N; i++) { // i = 0, 表示最左边的那头牛// 计算区间[i, i + K – 1]if((dir[i] + sum) % 2 != 0) { // 为奇数res++;f[i] = 1;}sum += f[i];if(i – K + 1 >= 0) {sum -= f[i – K + 1];}}// 检查最后面的情况（K- 1）头牛for(int i = N – K + 1; i < N; i++) {if((dir[i] + sum) % 2 != 0) {// 无解return -1;}if(i – K + 1 >= 0) {sum -= f[i – K + 1];}}return res;}int main() {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);while(scanf("%d", &N) != EOF) {//cout << N << endl;for(int i = 0; i < N; i++) {scanf("%d", &dir[i]);//cout << dir[i] << endl;}int K = 1;int M = N;for(int k = 1; k <= N; k++) {int m = calc(k);if(m >= 0 && M > m) {M = m;K = k;}}printf("%d %d \n", K, M);}}输入文件input.txt：71 1 0 1 0 1 1
编译运行后， 输出文件如下output.txt：
3 3
理想的路总是为有信心的人预备着
