反转（开关问题）　poj3276

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.

Input

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.

Output

Line 1: Two space-separated integers: K and M

Sample Input

7
B
B
F
B
F
B
B

Sample Output

3 3

Hint

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)

题意：有n头牛，知道每头牛朝前还是朝后。

　　机器每次可以使连续k头牛的朝向与原来相反，求出最少的操作次数及对应的k

分析：一开始看到这道题的时候，我以为又是个dp的题，想着二分枚举区间长度k，再根据k来跑dp.。

　　　结果发现我一点也没想对。。。。首先这个k好像不具有单调性，而且很多区间是重叠的，也就是子问题是重叠的，不能dp。

　　　后来去网上一查，这个题要用尺取法。。。

　　　首先每个区间最多翻转一次，翻转两次相当于没翻，翻三次相当于翻一次。

选择的区间可能是重叠的，所以我们无法独立判断需要翻转哪个区间。但是我们可以根据每个区间左端点的牛是否需要翻转来做，左端点的方向确定了，次段点的牛的方向也就确定了，再判断下一个区间是否需要翻转。以此类推，我们就可以求得答案。

　　　首先枚举k，再枚举每个牛是否需要翻转，再将区间的牛翻转，复杂度是n的三次方。这样是过不了的。

　　　我们可以在区间翻转的地方优化。对于当前的点，我们可以算出来以当前点结尾的区间中，所有牛的翻转次数,再进行判断（好像有点像单调队列），具体的就看代码吧。

 1 /*************************************************************************
 2     > File Name: k.cpp
 3     > Author: LiuGeXian
 4     > Mail: 1019630230@qq.com 
 5     > Created Time: 2020/4/7 12:52:01
 6  ************************************************************************/
 7 
 8 #include <iostream>
 9 #include <cstdio>
10 #include <cstring>
11 #include <algorithm>
12 using namespace std;
13 const int maxn = 5e3 + 5;
14 int n, a[maxn], flag[maxn];
15 int Jud(int k){
16     memset(flag, 0, sizeof(flag));//ans是牛需要翻转的次数
17     int sum = 0, ans = 0;//sum是以当前点结尾的长度为k的区间中所有牛翻转的次数
18     for (int i = 1; i + k - 1 <= n; i++){
19         if ((a[i] + sum)% 2 == 1){//flag[i]表示以i开头的长度为k的区间是否翻转
20             ans++;
21             flag[i] = 1;
22         }
23         sum += flag[i];
24         if (i - k + 1 >= 1){
25             sum -= flag[i - k + 1];
26         }
27     }
28     for (int i = n - k + 2; i <= n; i++){//此时无法再将长度为k的区间翻转
29         if ((a[i] + sum) % 2 == 1) return 0;//需要判断是否能符合条件
30         if (i - k + 1 >= 1)    sum -= flag[i - k + 1];
31     }
32     return ans;
33 }
34 int main(){
35     scanf("%d", &n);
36     getchar();
37     for (int i = 1; i <= n; i++){
38         char ch = getchar();
39         getchar();
40         if (ch == 'B')  a[i] = 1;//定义牛如果朝后为则a[i]为1否则为0
41         else a[i] = 0;
42     }
43     int t, ans = 0x7fffffff;
44     for (int k = 1; k <= n; k++){
45         int x = Jud(k);
46         if (x < ans && x != 0){
47                 t = k;
48                 ans = x;
49         }
50     }
51     cout << t << ' ' << ans;
52     return 0;
53 }

View Code

反转（开关问题） poj3276

反转（开关问题）　poj3276