Coloring Trees [Codeforces 369 : Div2 C] - はまやんはまやんはまやん

問題

http://codeforces.com/contest/711/problem/C

n本の木がある。
これらの木をm種類の色で塗る。
木iは色C[i]で塗られているが、一部(C[i]=0のもの)は色が塗られていない。
塗られていない木に色を塗っていくのだが、木iに色jを塗るときはp[i][j]のインクが必要。
木達の美しさを隣り合う色が同じ木をまとめた成分数と定義する。

2,1,1,1,3,2,2,3,1,3
であれば、隣り合う色が同じ木をまとめると
{2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}
となり成分数は7なので、美しさは7

この時塗られていない木を塗って、美しさをkとする時に必要な最小インク総数は？
不可能なときは-1を出力。

1 <= k <= n <= 100
1 <= m <= 100
0 <= c[i] <= m
1 <= p[i][j] <= 10^9

考察

1. 例の1番目が何も塗られてない木が3本あり、美しさを2にする問題
2. 何も塗られてない状況から考えろってこと？
3. ソートは順が関係あるから無理なんで、先頭から色を決定していく感じ？
4. 先頭から色を決定していくと、塗りたい木の1つ前の色だけに対応して美しさが増減する
5. だいぶ状態がまとめられそうだぞ・・・
6. しかも「最小」インク総数を求める
7. これは…DP!

8. DPを使って解きます

dp[i][j][k] = i番目まで塗って、最後の色がjで、今までの美しさがkである時の最小インク総数
初期化 : dp[0][0][0] = 0, dp[他] = INF
dp[i][j][k] -> 色ii(j == ii)を塗る dp[i + 1][ii][k] + P[j][ii]
            -> 色ii(j != ii)を塗る dp[i + 1][ii][k + 1] + P[j][ii]

9. これを元々色が塗ってある場合で場合分けをして拡張する
10. 場合分け先では、8.のDPでは全て色を塗るよう試したのに対し、塗られている色だけで塗る処理をする
11. この時はインクを使わないので、dpには特に何も足さない

12. 最後に答えをまとめて答える

実装

http://codeforces.com/contest/711/submission/20237906

#define INF 1LL<<60
typedef long long ll;
int N, M, K;
int C[101];
int P[101][101];

// dp[i][j][k] = i番目まで塗って、最後の色がjで、今までの美しさがkである時の塗る最小コスト
ll dp[101][101][101];
//-----------------------------------------------------------------
int main() {
	cin >> N >> M >> K;
	rep(i, 0, N) cin >> C[i];
	rep(i, 0, N) rep(j, 0, M) cin >> P[i][j + 1];
	
	rep(i, 0, N + 1) rep(j, 0, M + 1) rep(k, 0, K + 1) dp[i][j][k] = INF;
	dp[0][0][0] = 0;

	rep(i, 0, N) rep(j, 0, M + 1) rep(k, 0, K + 1) if(dp[i][j][k] != INF){
		if (C[i] == 0) {
			rep(ii, 1, M + 1) {
				int kk = k;
				if (j != ii) kk++;
				dp[i + 1][ii][kk] = min(dp[i + 1][ii][kk], dp[i][j][k] + P[i][ii]);
			}
		}
		else
		{
			int kk = k;
			if (j != C[i]) kk++;
			dp[i + 1][C[i]][kk] = min(dp[i + 1][C[i]][kk], dp[i][j][k]);
		}
	}

	ll ans = INF;
	rep(j, 1, M + 1) ans = min(ans, dp[N][j][K]);

	if (ans == INF) ans = -1;
	cout << ans << endl;
}