PKU演習問メモ(6/13)

何か土日疲れが出てて全然問題解けなかったなあ。
最近全然実力向上してないし、こんなんじゃますます停滞するよorz

No.	問題名	問題の種類および解法	難易度
2978	Colored stones	ビットDP	★★☆☆☆

2978 Colored stones

問題概要

m個の石の色が一列に並んでおり、それぞれの色は1...kのうちいずれかである。
m,k,各石の色が与えられたとき、列から石を取り除いて「どの同じ色の二つの石の間にも、他の色の石が入っていない」状態にしたい。

取り除く石の個数の最小値を求めよ。

解法

原文の問題文では、"What is the minimum number of stones you must remove so that no two stones of one color are separated by a stone of a different color"
なのだけど、これって二つの同色の石の間に違う色の石"1個"が挟まれないように、って読めちゃう気が……
それで3回ほどWA出した。

解法はビットDPによる。すなわち、[i個の石までの][その中に各石が含まれてるかのビット表現][右端の石の色]の最適解のテーブルを作って更新していく。

ソースコード

int m,k,color[100];
int dp[101][1<<6][6];

int main()
{
	while(cin>>m>>k,m)
	{
		rep(i,m)cin>>color[i];
		rep(i,m+1)rep(j,1<<k+1)fill_n(dp[i][j],k+1,inf);
		
		dp[0][0][0]=0;
		for(int i=1;i<=m;i++)rep(bit,1<<k+1)rep(j,k+1)
		{
			//not skip
			if(color[i-1]==j||(bit&1<<color[i-1])==0)
			dp[i][bit|1<<color[i-1]][color[i-1]]=
			min(dp[i][bit|1<<color[i-1]][color[i-1]],dp[i-1][bit][j]);
			
			//skip
			dp[i][bit][j]=min(dp[i][bit][j],dp[i-1][bit][j]+1);
		}
		int ans=m;
		rep(bit,1<<k+1)rep(i,k+1)ans=min(dp[m][bit][i],ans);
		
		cout<<ans<<endl;
	}
	
	return 0;
}