Codeforces #369 Div2 C. Coloring Trees

今回は割と簡単目。
http://codeforces.com/contest/711/problem/C

問題

N個の木を1～Mのいずれかの色で塗る。
一部の木iは既に色C[i]で塗られている。
まだ塗られていない木iにj番の色を塗るコストはP[i][j]である。

色を塗った結果、連続した同一の色の木を出来るだけ多く１つのグループとして扱うとする。

グループがK個となる塗り方のうち、塗るコストの最小値を求めよ。

解法

以下を状態にとり順にDPすればよい。
dp(i,c,g) := i番目までの木の色を確定させたとき、i番の木の色がcでそこまでg個グループがある場合の最小コスト

C[i]=0の木に対し色の塗り方はM通り試しても間に合う。その場合DPはO(N^2*M^2)かかる。
実際は「前の木と同じ色」「後ろの木と同じ色」「どちらとも違う色」とせいぜい３通り試せばいいのでO(N^2*M)で済ませることもできる。
ただ前者でも間に合うので、以下のコードは前者である。

int N,M,K;
int C[1010];
int A[110][110];
ll dp[110][110][110];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) cin>>C[i];
	FOR(y,N) FOR(x,M) cin>>A[y][x];
	
	memset(dp,0x3f,sizeof(dp));
	dp[0][0][0]=0;
	FOR(i,N) {
		FOR(x,M+1) {
			FOR(y,i+1) if(dp[i][x][y]<1LL<<59) {
				if(C[i]==0) {
					for(r=1;r<=M;r++) {
						if(x==r) dp[i+1][r][y] = min(dp[i+1][r][y],dp[i][x][y]+A[i][r-1]);
						else dp[i+1][r][y+1] = min(dp[i+1][r][y+1],dp[i][x][y]+A[i][r-1]);
					}
				}
				else {
					if(x==C[i]) dp[i+1][x][y] = min(dp[i+1][x][y],dp[i][x][y]);
					else dp[i+1][C[i]][y+1] = min(dp[i+1][C[i]][y+1],dp[i][x][y]);
				}
			}
		}
	}
	
	ll mi=1LL<<60;
	for(r=1;r<=M;r++) mi=min(mi,dp[N][r][K]);
	if(mi==1LL<<60) mi=-1;
	cout<<mi<<endl;
	
}

まとめ

面倒なだけで面白みは余り感じない？