# 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 ≤ KN)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)

这道题需要用到‘尺取法’，根据我在网上找的题解来看，这道题所用的尺取法就是依次选定我们更改的长度k，在我们需要操作的序列上依次进行区间修改。这就有点类似于贪心的思路。我们在反转时需要注意以下两点：

1、交换区间反转的顺序对结果是没有影响的。

2、对同一个区间进行两次以上的反转是多余的。

sum+=f[i];

if(i-k+1>=1) sum-=f[i-k+1];

``` 1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 const int N=5e3+10;
5 int n,f[N];
6 char c[N];
7 int cow(int k){
8     memset(f,0,sizeof(f));
9     int ans=0,sum=0;
10     for(int i=1;i<=n-k+1;++i){
11         if(sum%2==0&&c[i]==‘B‘)
12             f[i]=1,ans++;
13         else if(sum%2==1&&c[i]==‘F‘)
14             f[i]=1,ans++;
15         sum+=f[i];
16         if(i-k+1>=1) sum-=f[i-k+1];
17     }
18     for(int i=n-k+2;i<=n;++i){
19         if(sum%2==0&&c[i]==‘B‘) return -1;
20         else if(sum%2==1&&c[i]==‘F‘) return -1;
21         sum+=f[i];
22         if(i-k+1>=1) sum-=f[i-k+1];
23     }
24     return ans;
25 }
26 int main(){
27     scanf("%d",&n);
28     int m=2147483617,k;
29     for(int i=1;i<=n;++i) scanf(" %c",&c[i]);
30     for(int i=1;i<=n;++i){
31         int cnt=cow(i);
32         if(cnt>=0&&cnt<m)
33             k=i,m=cnt;
34     }
35     printf("%d %d\n",k,m);
36     return 0;
37 }```

## POJ3276 Face The Right Way 【尺取法】

Face The Right Way Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 2721   Accepted: 1246 Description 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 facin

## POJ 3320 尺取法，Hash，map标记

1.POJ 3320 2.链接:http://poj.org/problem?id=3320 3.总结:尺取法,Hash,map标记 看书复习,p页书,一页有一个知识点,连续看求最少多少页看完所有知识点 必须说,STL够屌.. #include<iostream> #include<cstring> #include<cmath> #include<queue> #include<algorithm> #include<cstdio>

## HDU 5672 String 尺取法追赶法

String Problem Description There is a string S.S only contain lower case English character.(10≤length(S)≤1,000,000)How many substrings there are that contain at least k(1≤k≤26) distinct characters? Input There are multiple test cases. The first line