题目大意：农夫有一群牛，牛排成了一排，现在需要把这些牛都面向正确的方向，农夫买了一个机器，一次可以处理k只牛，现在问你怎么处理这些牛才可以使操作数最小？
这道题很有意思，其实这道题是著名的开关问题的变种，我们可以用模拟去做，但是总不能一个一个地去翻转，不然就是2^n的复杂度了，我们要想另外一些方法。
我们知道，如果连续翻转同一片区域其实等于没有反转，再者，在翻转位置一样的情况下，先翻转谁其实没有太打大的关系，所以我们可以规定一个顺序（比如从左到右翻转），如果规定了一个方向翻转以后，我们可以翻转过后的左区域以后都不会受到影响，所以这样我们就可以像矩阵乘法一样把k不断增长来把复杂度降下去O(N^3)（K个长度，每个长度最多操作N个数，每个数翻转K次）但是这样对于N=5000来说还是太大了，我们要继续把复杂度降下去。
我们利用以前那种偏序集的方法，我们规定一个东西flip[i]:=i~i+k-1的是否需要翻转，如果需要翻转则是1，否则就是0,同时定义背面为1，正面是0
可以看到
∑((i+1)-k+1,i)flip[j]=∑(i-1,i-k+1)flip[j]+flip[i]-flip[i-k+1]
那么我们就可以不断减去两端的方法来求得flip的值了，这是个常数时间，所以复杂度降为O(N^2)
1 #include <iostream> 2 #include <algorithm> 3 #include <functional> 4 5 using namespace std; 6 7 static int dir[5001], if_flip[5001]; 8 9 int solve(const int, const int); 10 11 int main(void)//开关问题 12 { 13 int cows_sum, ans_k, ans_step, step; 14 char tmp; 15 while (~scanf("%d", &cows_sum)) 16 { 17 getchar(); 18 for (int i = 0; i < cows_sum; i++) 19 { 20 scanf("%c", &tmp); 21 dir[i] = tmp == 'B' ? 1 : 0;//0表示前面，1表示后面 22 getchar(); 23 } 24 ans_step = cows_sum; ans_k = 1; 25 for (int k = 1; k <= cows_sum; k++) 26 { 27 step = solve(cows_sum, k); 28 if (step >= 0 && step < ans_step) 29 { 30 ans_step = step; 31 ans_k = k; 32 } 33 } 34 printf("%d %d ", ans_k, ans_step); 35 } 36 return 0; 37 } 38 39 int solve(const int cows_sum,const int k) 40 { 41 //flip[i]:=i~i+k-1是否进行了翻转，翻转了就是1，否则就是0 42 int sum = 0, i, ans_step = 0; 43 44 memset(if_flip, 0, sizeof(if_flip)); 45 for (i = 0; i <= cows_sum - k; i++) 46 { 47 if ((dir[i] + sum) % 2 == 1)//表明经过一系列翻转（如存在）还是背面朝上，则继续翻转 48 { 49 ans_step++; 50 if_flip[i] = 1; 51 } 52 sum += if_flip[i]; 53 if (i - k + 1>= 0)//注意这里是i-k+1！ 54 sum -= if_flip[i - k + 1]; 55 } 56 for (; i < cows_sum; i++)//检查，剩下的段是不能翻转了(小于k了，所以只用检查一下符不符合规则就好) 57 { 58 if ((dir[i] + sum) % 2 == 1)//说明还是有朝上的，说明这样的k是不行的 59 { 60 ans_step = -1; 61 break; 62 } 63 else if (i - k + 1>= 0)//注意这里是i-k+1！ 64 sum -= if_flip[i - k + 1]; 65 } 66 return ans_step; 67 }
