TopCoder SRM 589 Div 2第2題

タイプ:DP難易度:2
标题:一山の歯車が2つずつ隣接して1周して、各歯車の回転方向を与えて、歯車の首尾がつながって、すなわちn個の歯車、0とn-1が隣接して、歯車は左右に隣接する歯車の方向と逆になってやっと回転することができて、1つの歯車を取り除いて、左右の歯車は隣接していると見なさないで、少なくともいくつかの歯車を取り除いて、残りの歯車がすべて所定の方向に回転することを保証することができます.ギア方向はL,Rで表します.
 
解析:dp問題は、i番目のギアを除去し、0からiまで合計で除去したギア数の最小値をdp[i][0]で記憶し、dp[i][1]はi番目のギアを除去せず、0からiまで合計で除去したギア数の最小値を示す
繰返し式:dp[i][0]=min(dp[i-1][0],dp[i-1][1])+1
現在の歯車が前の方向と異なる場合:dp[i][0]=min(dp[i-1][0],dp[i-1][1])
その他:dp[i][1]=dp[i-1][0]
最後のmin(dp[n-1][0],dp[i-1][1])は求められる
しかし、歯車は首尾が連結されているため、最後の歯車が第1の歯車と同じ方向であるかどうかを考慮し、f[i][0]でdp[i][0]を記録して最小値をとると、第1の歯車が取り除かれるかどうかを考慮する.f[i][1]記録dp[i][1]最小値をとると、1番目のギアが抜けていないか
最後に、最後の1つが第1の方向と同じでdp[n−1][1]が最も小さいときに第1の歯車が存在すると、dp[n−1][1]++は、第1の歯車を除去して回転する必要がある.
コードは次のとおりです.
 

#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;

#define MIN(x,y) (x)<(y)?(x):(y)

const int MAX = 55;
class GearsDiv2
{
	public:		
		int dp[MAX][2];
		bool first[MAX][2]; 
		int getmin(string Directions)
		{
			memset(dp,0,sizeof(dp));
			memset(first,0,sizeof(first));
			
			int n = Directions.length();
			
			dp[0][0] = 1;
			dp[0][1] = 0;
			first[0][0] = 1;
			first[0][1] = 0;
			for(int i=1; i<n; i++)
			{
				if(dp[i-1][0] < dp[i-1][1])
				{
					dp[i][0] = dp[i-1][0]+1;
					first[i][0] = first[i-1][0];
				}
				else if(dp[i-1][0] > dp[i-1][1])
				{				
					dp[i][0] = dp[i-1][1]+1;
					first[i][0] = first[i-1][1];
				}
				else 
				{
					dp[i][0] = dp[i-1][1]+1;
					first[i][0] = first[i-1][1] | first[i-1][0];
				}
				
				if(Directions[i]!=Directions[i-1])
				{
					dp[i][1] = dp[i][0] - 1;
					first[i][1] = first[i][0];
				}
				else
				{
					dp[i][1] = dp[i-1][0];
					first[i][1] = first[i-1][0];
				}
			}
			if(n>2)
			{
				if(Directions[n-1]==Directions[0] && !first[n-1][1])
				{
					dp[n-1][1]++;
				}
			}
			
			return MIN(dp[n-1][0],dp[n-1][1]);
		}
};