TopCoder SRM 351 Div1 Medium BoxesArrangement

問題

A,B,C三種類からなる文字列が与えられる。
この文字列を、二つの文字を選び、その位置を入れ替えるような操作を繰り返して、「連続する3つの文字が同じ文字になっている」部分がないようにしたい。

このとき、"入れ替えの操作で触らなかった"文字の数を最大にしたい。
触らない文字の数の最大値はいくつか、求めよ。

制約条件

文字数≦50

方針

Aをa個,Bをb個,Cをc個、条件を満たすように並べながら、ペナルティを最小にすると考えても同じ。

動的計画法による。
dp[a][b][c][prev][continue]を、
Aをa文字使い、Bをb文字使い、Cをc文字使い、
一個前の文字がprevで、今その文字がcontinue文字だけ続いているような状態における、
不一致の文字の数の最小値とする。

これを更新していくようなDPをすればよい。

ソースコード

//A, B, C, prev, continue
int dp[51][51][51][3][3];
class BoxesArrangement {
	public:
	int maxUntouched(string boxes) 
	{
		int n=boxes.size();
		rep(i,n+1)rep(j,n+1)rep(k,n+1)rep(l,3)rep(m,3)dp[i][j][k][l][m]=inf;
		dp[0][0][0][0][0]=0;
		rep(p,n)rep(i,p+1)rep(j,p+1-i)rep(k,p+1-i-j)if(i+j+k==p)rep(l,3)rep(m,3){
			if(dp[i][j][k][l][m]!=inf)rep(cl,3){
				int ni=i+(cl==0), nj=j+(cl==1), nk=k+(cl==2);
				int nc=l==cl?m+1:1, ncost=dp[i][j][k][l][m]+(boxes[p]-'A'!=cl);
				if(nc>2)continue;
				dp[ni][nj][nk][cl][nc]=min(dp[ni][nj][nk][cl][nc],ncost);
			}
		}
		int a=0, b=0, c=0, ans=inf;
		rep(i,n){
			if(boxes[i]=='A')a++;
			if(boxes[i]=='B')b++;
			if(boxes[i]=='C')c++;
		}
		rep(i,3)rep(j,3)ans=min(ans,dp[a][b][c][i][j]);
		return ans==inf?-1:n-ans;
	}
};