SRM 643 div1 med: TheKingsArmyDiv1
動的計画法で解きたかった。
問題:TopCoder Statistics - Problem Statement
解法:動的計画法を使う。dp[l][r][k]を,
k=0:区間[l,r)の上半分をHにするのに必要な最小回数
k=1:区間[l,r)の下半分をHにするのに必要な最小回数
k=2:区間[l,r)の全体をHにするのに必要な最小回数
として,幅の長さに合わせてDPする。正直なんでこれで通るのかイマイチかも…
const int MAXN = 202; // 0: 0行をすべてHにする 1: 1行をすべてHにする 2: 0,1行をすべてHにする int dp[MAXN][MAXN][3]; const int INF = 1e9; class TheKingsArmyDiv1 { public: int getNumber(vector <string> state) { int n = state[0].size(); for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) for (int k = 0; k < 3; k++) dp[i][j][k] = INF; // dp for (int i = 0; i < n; i++) { char c1 = state[0][i], c2 = state[1][i]; if (c1 == 'H' && c2 == 'H') { dp[i][i+1][0] = 0; dp[i][i+1][1] = 0; dp[i][i+1][2] = 0; } else if (c1 == 'H' && c2 == 'S') { dp[i][i+1][0] = 0; dp[i][i+1][1] = 1; dp[i][i+1][2] = 1; } else if (c1 == 'S' && c2 == 'H') { dp[i][i+1][0] = 1; dp[i][i+1][1] = 0; dp[i][i+1][2] = 1; } } for (int w = 1; w <= n; w++) { for (int l = 0; l+w <= n; l++) { // [l, r) int r = l+w; // [l, k) と[k, r)に分ける for (int k = l+1; k < r; k++) { dp[l][r][0] = min({dp[l][r][0], dp[l][k][0]+dp[k][r][0], dp[l][k][0]+r-k, dp[k][r][0]+k-l}); dp[l][r][1] = min({dp[l][r][1], dp[l][k][1]+dp[k][r][1], dp[l][k][1]+r-k, dp[k][r][1]+k-l}); dp[l][r][2] = min({dp[l][r][2], dp[l][k][2]+dp[k][r][2], dp[l][k][2]+r-k, dp[k][r][2]+k-l, dp[l][r][0]+1, dp[l][r][1]+1}); dp[l][r][0] = min(dp[l][r][0], dp[l][r][2]); dp[l][r][1] = min(dp[l][r][1], dp[l][r][2]); } } } return dp[0][n][2] >= INF ? -1 : dp[0][n][2]; } };