[POJ3276]Face The Right Way

题目

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头奶牛排成一队，有的脸朝前有的脸朝后，F代表前，B代表后。现在有一种操作可以让连续K头奶牛同时反转，问至少要反转多少次，此时K至少为多少。先输出K，再输出最小反转次数。

显然我们需要从1到n挨个尝试K的可能取值，并从中选取最优，主要问题在于怎么算K一定时的最小反转次数呢？自然想到遍历区间。从[1,k]区间遍历到[n-k+1,n]，对于每一个区间，如果区间的第一个是反的，那么我们就把整个区间反转。当然我们不可能直接修改原数组因为后面还要用，那么我们就用一个sum标记前k-1修改了多少次来确定当前是否需要修改。

（部分解释放在了代码里）

代码

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm> 
 5 using namespace std;
 6 const int maxn=5000+3;
 7 int a[maxn],n,flag[maxn];
 8 int solve(int k){
 9     int i;
10     memset(flag,0,sizeof(flag));
11     //flag[i]表示区间[i,i+k-1] 是否需要翻转
12     int sum=0,cnt=0;//前k-1个转变的次数
13     for(i=1;i<=n-k+1;i++){
14     //sum记录走到当前i，其前面k-1个翻转了多少次
15         if(i-k>=1){
16             sum-=flag[i-k];
17         }
18         if(a[i]==0&&sum%2==0){
19         //如果是B 且前面翻转了偶数次 仍旧需要翻转
20              flag[i]=1;
21              sum+=flag[i];
22              cnt++;
23         }
24         else if(a[i]==1&&sum%2==1){
25         //如果是F  且前面翻转了奇数次
26             flag[i]=1;
27             sum+=flag[i];
28             cnt++;
29         }
30     }
31     for(i;i<=n;i++){
32         if(i-k>=1)
33         {
34             sum-=flag[i-k];
35         }
36         if(sum%2==0&&a[i]==0) return -1;
37         else if(sum%2==1&&a[i]==1) return -1;
38     }
39     return cnt;
40 }
41 int main(){
42     int k=1,Max;
43     char s[1];
44     scanf("%d",&n);
45     Max=100010000;
46     for(int i=1;i<=n;i++){
47         scanf("%s",s);
48         if(s[0]=='B') a[i]=0;
49         else if(s[0]=='F') a[i]=1;
50     }
51     for(int i=1;i<=n;i++){
52         int mid=solve(i);
53         if(mid==-1) continue;
54         if(Max>mid){
55             Max=mid;
56             k=i;
57         }
58     }
59     printf("%d %d",k,Max);
60     return 0;
61 }

View Code

幸甚至哉，歌以咏志。