TopCoder SRM 596 Div2 Medium ColorfulRoad

あれ、今回もDiv2 MediumはDiv1にない問題だ。
http://community.topcoder.com/stat?c=problem_statement&pm=12837

問題

0～(N-1)番まで一列に並んだN(<=15)マスからなる道があり、それぞれR,G,Bのいずれかの色がついている。
0番マスから(N-1)番マスに移動したいが、以下のルールを満たさなければならない。

• 移動は数字が増える方向のみ可能。
• 移動するマスはR→G→B→Rの順でなければならない。
• Pマス移動したらP*P分のコストがかかる。

(N-1)番マスまで移動する最小コストを答えよ。

解法

N<=15なので、止まるマスをbitDPで決めてしまえばよい。
後は上記条件を実装するだけ。

class ColorfulRoad {
	public:
	int getMin(string road) {
		int L=road.size();
		int ma=1000000,mask;
		
		FOR(mask,1<<L) {
			if((mask&1)==0 ||  (mask&(1<<(L-1)))==0) continue;
			int t=0,pre=0,i;
			for(i=1;i<L;i++) {
				if(mask&(1<<i)) {
					t+=(i-pre)*(i-pre);
					if(road[pre]=='R' && road[i]!='G') t+=1000000;
					if(road[pre]=='G' && road[i]!='B') t+=1000000;
					if(road[pre]=='B' && road[i]!='R') t+=1000000;
					pre=i;
				}
			}
			ma=min(t,ma);
		}
		
		return (ma==1000000)?-1:ma;
	}
};

まとめ

なんか今回Div1 Easy,Mediumといいbit処理問題が多いな。