SRM 688 div2 easy ParenthesesDiv2Medium
問題概要
カッコの文字列が与えられる。カッコが対応する形に変更する。ただし変更できる文字の数は、((文字数)/2)+1まで。
解法
動的計画法で解いた。変更できる文字の数に制限があるので、最小の数で対応づけができるものを求めた。dp[i][j] := i番目までみて、'('がj個多い時の変更した最小回数 として、ループで値を埋めていった。注意することは漸化式を立てるときに、j=0の時だけ場合分けしなければならない。j=0の時に、次に、')'を置くと、j=-1となり、カッコが対応しなくなるから。
これで最小値は求まるが、どこの位置を変更したかも求めなければならない。そのため経路復元用に、back[i][j] := i番目まで見て、'('がj個多いときにどちらをつかったか、0なら'(' 1なら')' としてどちらを選んだかを記憶しておく。復元用配列は、dp配列と同じようにとればよい。backを逆方向にたどり、どちらを使ったかをメモし、そこからどのような文字列をつくったか求め、元の位置と異なっている箇所が変更した箇所となる。
ミス
もともと対応しているカッコを除外して、そのほかの部分を変える解法。だいぶ楽に書けるみたい。
コード
#include <iostream> #include <string> #include <vector> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; //dp[i][j] := i番目までみて、'('がj個多い時の変更した最小回数 int dp[55][30]; //back[i][j] := i番目まで見て、'('がj個多いときにどちらをつかったか、0なら'(' 1なら')' int back[55][30]; class ParenthesesDiv2Medium{ public: vector <int> correct(string s){ rep(i, 55)rep(j, 30) dp[i][j] = INF; dp[0][0] = 0; for (int i = 0; i < s.size(); ++i){ for (int j = 0; j <= s.size() / 2; ++j){ if(j == 0){//'('のみしかおけない if(s[i] == '('){ if(dp[i][j] < dp[i + 1][j + 1]){ dp[i + 1][j + 1] = dp[i][j]; back[i + 1][j + 1] = 0; } }else{ if(dp[i][j] + 1 < dp[i + 1][j + 1]){ dp[i + 1][j + 1] = dp[i][j] + 1; back[i + 1][j + 1] = 0; } } }else{ if(s[i] == '('){ //'('をおく if(dp[i][j] < dp[i + 1][j + 1]){ dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]); back[i + 1][j + 1] = 0; } //')'をおく if(dp[i][j] + 1 < dp[i + 1][j - 1]){ dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + 1); back[i + 1][j - 1] = 1; } }else{ //'('をおく if(dp[i][j] + 1 < dp[i + 1][j + 1]){ dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1); back[i + 1][j + 1] = 0; } //')'をおく if(dp[i][j] < dp[i + 1][j - 1]){ dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j]); back[i + 1][j - 1] = 1; } } } } } //復元 vector<int> ans; int now = 0; for (int i = s.size(); i > 0; --i){ if(back[i][now] == 0){ ans.push_back(0); now--; }else{ ans.push_back(1); now++; } } reverse(ans.begin(), ans.end()); string tmp = ""; rep(i, ans.size()){ if(ans[i] == 0) tmp += '('; else tmp += ')'; } vector<int> ret; rep(i, s.size()){ if(s[i] != tmp[i]){ ret.push_back(i); } } return ret; } };