POJ 3691 DNA repair
蟻本の文字列の章読んでたら出てきたので解きました。POJ めっちゃ久しぶりや… 前やった SRM の問題に似てます。mayokoex.hatenablog.com
解法
蟻本に書いてあるとおり。
const int MAXK = 1000; const int MAXLEN = 1010; const int INF = 1e8; const string AGCT = "AGCT"; int nextState[MAXK][4]; bool ng[MAXK]; int dp[MAXLEN][MAXK]; int solve(const vector<string>& ngWords, const string& init) { vector<string> pfx; int n = ngWords.size(); // 状態の列挙 for (int i = 0; i < n; i++) { string s = ngWords[i]; for (int j = 0; j <= (int)s.size(); j++) { pfx.push_back(s.substr(0, j)); } } sort(pfx.begin(), pfx.end()); pfx.erase(unique(pfx.begin(), pfx.end()), pfx.end()); int K = pfx.size(); // 状態の遷移 for (int i = 0; i < K; i++) { for (int j = 0; j < 4; j++) { string s = pfx[i] + AGCT.substr(j, 1); while (1) { int nk = lower_bound(pfx.begin(), pfx.end(), s) - pfx.begin(); if (nk < K && pfx[nk] == s) { nextState[i][j] = nk; break; } s = s.substr(1); } } } // 状態がngかどうか for (int i = 0; i < K; i++) { ng[i] = false; int sl = pfx[i].size(); for (int j = 0; j < n; j++) { int wl = ngWords[j].size(); if (sl < wl) continue; if (pfx[i].substr(sl-wl) == ngWords[j]) { ng[i] = true; break; } } } // dp int length = init.size(); for (int i = 0; i <= length; i++) for (int k = 0; k < K; k++) { dp[i][k] = INF; } dp[0][0] = 0; for (int l = 0; l < length; l++) for (int k = 0; k < K; k++) { if (dp[l][k] == INF) continue; if (ng[k]) continue; for (int j = 0; j < 4; j++) { int plus = (init[l] == AGCT[j]) ? 0 : 1; int ns = nextState[k][j]; if (ng[ns]) continue; dp[l+1][ns] = min(dp[l][k]+plus, dp[l+1][ns]); } } int ans = INF; for (int k = 0; k < K; k++) { if (ng[k]) continue; ans = min(ans, dp[length][k]); } if (ans == INF) ans = -1; return ans; } int main() { cin.tie(0); ios::sync_with_stdio(false); int T = 0; int n; while (cin >> n) { if (n == 0) break; T++; vector<string> ngWords; for (int i = 0; i < n; i++) { string s; cin >> s; ngWords.push_back(s); } string init; cin >> init; printf("Case %d: %d\n", T, solve(ngWords, init)); } return 0; }