POJ 3276 Face The Right Way

POJ 3276 Face The Right Way

Face The Right Way Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 2665 Accepted: 1233

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)

算法分析：

大概題意就是有n頭牛，在一條直線上，有著不同的方向，前和後，現在讓你尋找一個k值，使得每次都只能反轉k頭牛，求解最少次數與最小k。

當第一次看這個問題時，覺得還是有點棘手的，因為想改變一頭牛的方向就必定影響k頭牛，但在思考一下，當一頭牛被反轉2的倍數次時，與初始方向相同，可視為無反轉，因為要枚舉k並進行N-K+1（最壞情況）次反轉，且每次翻轉要不斷改變dir（方向數組）數組的值，所以復雜度O（N^3）,超時，但對於反轉改變數值我們可以考慮用一個新的數組f[i]來解決。借助f[i]（0或1）來存儲每一個位置的反轉情況，進而使得復雜度降低為O（N^2）基於此代碼如下：

#include
using namespace std;
#define MAXN 5000
int dir[MAXN];                   //牛的方向，0 F 1 B
int f[MAXN];                     //記錄每個位置是否發生反轉，奇數反轉，偶數可視為沒發生反轉
int N;        
int calc(int k)
{
	int i,sum=0,res=0;           //用sum記錄i前面發生的對"當前"f[i]有影響的反轉次數，res記錄總的反轉次數
	memset(f,0,sizeof(f));
	for(i=0;i+k<=N;i++)              //注意結束條件i>n-k,即i=n-k+1
	{
		if((dir[i]+sum)%2!=0)
		{
			res++;
			f[i]=1;
		}
		sum+=f[i];
		//sum的值來自於記錄被反轉的次數，若當前i超出k范圍，
		//那麼i+1-k及其前面位置發生的反轉將不能影響當前i的反轉次數，所以減去
		if(i+1>=k)
			sum-=f[i+1-k];                   
		
	}
	for(i=N-k+1;i=k)
			sum-=f[i+1-k];                   
		
	}
	return res;
}
void solve()
{
	int p,q,ans=N+1;
	for(int i=1;i<=N;i++)
	{
		p=calc(i);
		if(p!=-1)
		{
			ans=(ansN;
	char c;
	int i;
	for(i=0;i>c;
		dir[i]=(c=='F'?0:1);
		getchar();
	}
	solve();
	
	return 0;
}