mayoko’s diary

プロコンとかいろいろ。

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];
    }
};