POJ 3276：Face The Right Way （开关问题）

POJ 3276：Face The Right Way （开关问题）

Face The Right Way

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 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)

题意：给出牛的起始状态，B为向后，F为向前，我们每次可以翻转连续区间的牛的方向，问最少的次数可以让所有的牛都达到向前状态的区间与次数。

对这道题目来说我们可以枚举区间大小，由题意我们可以知道翻转后面的牛不会影响前面牛的状态，但是翻转前面的牛会让后面所在区间中所有的牛都会翻转，并且同一个牛翻转两次相当于没有翻转，根据这样的关系，我们可以得到翻转一次以后所有牛的状态，如果到最后还有牛的方向不是向前，那就是当前翻转的区间失效啦！也就是不能翻转，继续枚举。

AC代码：

#include #include#include#include#define max(a,b) (a>b?a:b)using namespace std;int df[5100]; //'F':0 'B':1int f[5100]; //当前位是否被反转过int solve(int k,int N){ memset(f,0,sizeof(f)); int ans=0,sum=0; for(int i=0; i+k<=N; i++) { if((sum+df[i])&1)ans++,f[i]=1; //需要反转当前位 sum+=f[i]; //以后每位被反转的总次数 if(i-k+1>=0)sum-=f[i-k+1]; //取消第i-k+1的状态 } for(int i=N-k+1; i=0)sum-=f[i-k+1]; } return ans;}int main(){ int N; char c; scanf("%d%*c",&N); for(int i=0; i=0&&cou

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。