题目描述
Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.
Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.
Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.
N头牛排成一列1<=N<=5000。每头牛或者向前或者向后。为了让所有牛都 面向前方，农夫每次可以将K头连续的牛转向1<=K<=N，求操作的最少 次数M和对应的最小K。
输入格式
Line 1: A single integer: N
Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.
输出格式
Line 1: Two space-separated integers: K and M
样例
样例输入
1 7 2 B 3 B 4 F 5 B 6 F 7 B 8 B
样例输出
1 3 3
题目大意
有n头奶牛排成一排，有的朝前有的朝后，现在你可以使k(每次翻转必须是k头)头奶牛一次性翻转朝向(n>=k>=1)，问你最少的翻转次数和此时对应的k值。
分析
题目中给出了两种字母B和F，很显然，用字符数组写代码很不方便，所以我们将B转化为0，F转化为1
那么这道题就变成了将一个只含有0和1的数组进行多次取反，使得最终数组里的元素全都变成1
1 for(int i=1;i<=n;i++){ 2 scanf(" %c",&s); 3 if(s=='B') a[i]=0; 4 else a[i]=1; 5 }
这道题暴力还是比较好想的，我们可以将每次操作反转的长度k从1到n开始枚举
对于每一个k值，我们从1到n枚举长度为k的区间
因为同一个点翻转两次就与没有翻转的效果相同了，因此我们有一个贪心策略为：
从左到右对于出现的每一个B翻转一次
从当前点开始的区间，就能保证是最优解。
如果f[i]=0，那么把f[i]到f[i+k-1]这个长度为k的区间中的元素全部取反
取反后继续从i+1遍历，重复上一步
这样，从1到n的每一个值，我们都需要把它进行一次遍历
时间复杂度为n^3
1 int solve(int k) { 2 int ans = 0; 3 int i; 4 for(i = 1; i + k - 1 <= N; i++) { 5 if(f[i] == 1) { 6 for(int j = i; j <= i + k - 1; j++) { 7 f[j] = !f[j]; 8 } 9 ans++; 10 } 11 } 12 for(i--; i <= N; i++) { 13 if(f[i] == 1) return -1; 14 } 15 return ans; 16 }
很显然n=5000的数据过不了，不过还是可以拿一部分分的
优化
n^3的复杂度过不了，我们可以考虑省去一重循环，把它变成n^2
第一层是枚举区间k的大小，这一层我们显然不能省去，枚举每一个元素也不能省去
而且它们也不具有单调性，因此二分也不可以
那么我们再重新考虑一下操作的性质
对于一个数，如果对它操作偶数次，那么相当于没有操作
如果对它操作奇数次，那么相当于取反一次
所以我们没有必要去记录每一个的状态，我们只需要存储每一个元素被反转的次数
那么我们就可以用差分数组（名称为cf）记录该元素被操作的次数
如果该元素是1，那么它被操作偶数次才符合要求，如果是0就要操作奇数次
所以如果当前元素不符合要求，那我们就更新操作数,把cf[i]++,同时要把f[i+k-1]--，因为该操作只对[i,i-k+1]这个区间有效
1 if((a[i]+cf[i])%2==0){ 2 cf[i]++; 3 cf[i+k]--; 4 js++; 5 }
维护代码如上
那么什么情况下不成立呢？
很简单，当序列后面的元素数目不足k-1个的时候,判定这个k不成立直接跳过去
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=5010; 7 char s; 8 int a[maxn],cf[maxn];//cf差分数组,a原始数组 9 int n; 10 int solve(int k){ 11 int js=0;//记录区间取反的个数 12 memset(cf,0,sizeof(cf));//不要忘了初始化 13 for(int i=1;i<=n;i++){ 14 cf[i]+=cf[i-1];//维护差分数组 15 if(i+k-1<=n){ 16 if((a[i]+cf[i])%2==0){ 17 cf[i]++; 18 cf[i+k]--; 19 js++; 20 }//如果这个节点仍然是0，操作数加一 21 }else{ 22 if((a[i]+cf[i])%2==0){ 23 return 0x3f3f3f3f; 24 }//上面讲的不成立的情况 25 } 26 } 27 return js; 28 } 29 int main(){ 30 scanf("%d",&n); 31 for(int i=1;i<=n;i++){ 32 scanf(" %c",&s); 33 if(s=='B') a[i]=0; 34 else a[i]=1; 35 } 36 int cd=1,cx=n;//cx记录最小反转次数,cd记录操作的区间长度 37 for(int i=1;i<=n;i++){ 38 int ans=solve(i); 39 if(ans!=0x3f3f3f3f && ans<cx){ 40 cd=i; 41 cx=ans;//如果成立，更新 42 } 43 } 44 printf("%d %d ",cd,cx); 45 return 0; 46 }