SRM 509 div1 med:PalindromizationDiv1
SRM509の練習会に参加しました。easyだけ通しただけです。確か練習会ではmedを通した人がいなかったんですがmedは本番も異様に正解率低かったですね。僕も20回ぐらい提出してやっとACしました()
今回のeasyは簡単すぎると思うので省略します。
解法
基本的には区間DPです。
dp[l][r] = (区間[l, r]を回文にするためにかかる最低コスト)
とします。回文にするためには端っこから攻めていけば良いです。具体的には,
・word[l]を消してさらに[l+1, r]で回文にする
・word[r]を消してさらに[l, r-1]で回文にする
・word[l]の左にword[r]と同じ文字を追加してさらに[l, r-1]で回文にする
・word[r]の右にword[l]と同じ文字を追加してさらに[l+1, r]で回文にする
・端っこを両方共同じ文字に変えてさらに[l+1, r-1]で回文にする
・word[l]の左を変更してword[r]の右にその文字を追加し,さらに[l+1, r]で回文にする
・word[r]の右を変更してword[l]の左にその文字を追加し,さらに[l, r-1]で回文にする
最後の3つになかなか気づきませんでした…(しかもサンプルは通るっていう…)
で,このアイデアと同時に,すこし注意すべきことがあって,例えば文字aからbに直接変更するのは100かかるけど文字cを経由するとa->cにコスト1でc->bにコスト2だからこっちで文字を変えるほうがお得みたいなことがあります。文字の追加,消去についても同様です。
これを最初にワーシャルフロイドで処理しましょう(これも結構難しいアイデアな気がする)。
int n; const ll INF = 1e9; ll add[30], erase[30], change[30][30]; string word; ll dp[55][55]; int parse(string s) { int ret = 0; for (char c : s) { ret = ret*10 + (c-'0'); } return ret; } // [l, r] ll dfs(int l, int r) { if (l >= r) return 0; ll& ret = dp[l][r]; if (ret != -1) return ret; ret = INF; int cl = word[l]-'a'; int cr = word[r]-'a'; // 消す ret = min(ret, erase[cl]+dfs(l+1, r)); ret = min(ret, erase[cr]+dfs(l, r-1)); // 追加する ret = min(ret, add[cl]+dfs(l+1, r)); ret = min(ret, add[cr]+dfs(l, r-1)); // 変える for (int i = 0; i < 30; i++) { ret = min(ret, change[cl][i]+change[cr][i]+dfs(l+1, r-1)); ret = min(ret, change[cl][i]+add[i]+dfs(l+1, r)); ret = min(ret, change[cr][i]+add[i]+dfs(l, r-1)); } return ret; } class PalindromizationDiv1 { public: int getMinimumCost(string Word, vector <string> operations) { // input word = Word; n = word.size(); for (int i = 0; i < 30; i++) { add[i] = INF; erase[i] = INF; } for (int i = 0; i < 30; i++) { for (int j = 0; j < 30; j++) { change[i][j] = INF; } change[i][i] = 0; } memset(dp, -1, sizeof(dp)); for (auto s : operations) { if (s.substr(0, 3) == "add") { add[s[4]-'a'] = parse(s.substr(6)); } else if (s.substr(0, 5) == "erase") { erase[s[6]-'a'] = parse(s.substr(8)); } else { change[s[7]-'a'][s[9]-'a'] = parse(s.substr(11)); } } // warshall // change for (int k = 0; k < 30; k++) { for (int i = 0; i < 30; i++) { for (int j = 0; j < 30; j++) { change[i][j] = min(change[i][j], change[i][k] + change[k][j]); } } } // add/erase for (int k = 0; k < 30; k++) { for (int i = 0; i < 30; i++) { for (int j = 0; j < 30; j++) { add[i] = min(add[i], add[j]+change[j][i]); erase[i] = min(erase[i], erase[j]+change[i][j]); } } } int ans = dfs(0, n-1); if (ans == INF) return -1; return ans; } };