SRM 493 div1 med:AmoebaCode
解法
気づくべきなのは一つで, 答えは必ず K 以下になる, ということです。かっこ良く言うと鳩の巣原理からわかりますが, まぁ明らかでしょう。
ということで, dp[n][state] = n 番目の文字を見ている時点で, 状態が state である際の, スコアの最大値
とします。状態では,
(1 が連続で現れていない回数)
(2 が連続で現れていない回数)
...
(K が連続で現れていない回数)
を数にして記録しておきます。「連続で現れていない回数」は, 例えば 122461 という数列があったら, 4 のところまで見ると 1 が連続で現れていない回数は 3, 6 のところまで見ると 1 が連続で現れていない回数は 4, 最後の 1 のところまで見ると1 が連続で現れていない回数は 0, となります。
state のところで, k が連続で現れていない回数 (1 <= k <= K) として, K 以上の数は無視して良い(答えは必ず K 以下になるので)のが肝です。
dp の遷移はほとんど自明なのであとは実装をがんばります。
class AmoebaCode { public: int find(string code, int K) { int allState = 1; for (int i = 0; i < K; i++) allState *= K; int n = code.size(); vi dp(allState); dp[allState-1] = K; for (int i = 0; i < n; i++) { vi _dp(allState); for (int s = 0; s < allState; s++) { if (dp[s] == 0) continue; vi st(K); { int tmp = s; for (int j = K-1; j >= 0; j--) { st[j] = tmp%K; tmp /= K; } } if (code[i] != '0') { int ns = 0, score = dp[s]; for (int j = 0; j < K; j++) { if (code[i]-'0' == j+1) { ns = ns*K+0; score = min(score, st[j]+1); } else { ns = ns*K + min(K-1, st[j]+1); } } _dp[ns] = max(_dp[ns], score); } else { for (int j = 0; j < K; j++) { int ns = 0, score = dp[s]; for (int k = 0; k < K; k++) { if (k == j) { ns = ns*K + 0; score = min(score, st[k]+1); } else { ns = ns*K + min(K-1, st[k]+1); } } _dp[ns] = max(_dp[ns], score); } } } dp = _dp; } int ret = 0; for (int i = 0; i < allState; i++) ret = max(ret, dp[i]); return ret; } };