SRM693 Div1 Easy "BiconnectedDiv1"

問題

TopCoder Statistics - Problem Statement

解法

w1[i]を消すとw2[i-1]とw2[i]が消せなくなり、w2[i]を消すとw1[i], w1[i+1], w2[i-1], w2[i+1]が消せなくなる。
で、w1とw2を交互に、iの小さいものから消すか？消さないかを順に考えていけば、

w1[1]->w2[1]->w1[2]->w2[2]->w1[3]->w2[3]->...

w1[i]を消すとw2[i]が消せなくなり、w2[i]を消すとw1[i+1], w2[i+1]が消せなくなる。というのだけ考えればよくなる。

これを踏まえdpる。

dp[x] := (w1とw2の辺を交互に混ぜたうえで)x-1番目の辺まで考えた時の、消した辺の最大の重み。

初期化

まだ考えていなければ重みは0なので
dp[0] = 0;

更新

w1(混ぜた辺のインデックス(base-0)が偶数のもの)の辺を考えるとき、それを消さなければ
dp[i+1] = max(dp[i+1], dp[i])
それを消したら
dp[i+2] = max(dp[i+2], dp[i] + 辺iの重み)

w2(混ぜた辺のインデックス(base-0)が奇数のもの)の辺を考えるとき、それを消さなければ
dp[i+1] = max(dp[i+1], dp[i])
それを消したら
dp[i+3] = max(dp[i+3], dp[i] + 辺iの重み)

事後

問題文が齟齬なく読めた！バグもなかった！Systestも一発で通った！わはーい！

ソースコード

int dp[222];

class BiconnectedDiv1 {
    public:
    int minimize(vector<int> w1, vector<int> w2) {
        // w1, w2まぜまぜ
        vector<int> es;
        for (int i = 1; i < w1.size() - 1; i++) {
            es.push_back(w1[i]);
            if (i != w1.size() - 2) es.push_back(w2[i]);
        }

        // dp初期化
        int m = es.size();
        for (int i = 0; i <= m + 1; i++) {
            dp[i] = 0;
        }

        // dp更新
        for (int i = 0; i < m; i++) {
            // この辺は消さない
            dp[i + 1] = max(dp[i + 1], dp[i]);
            // この辺は消す
            int ni = i + (i % 2 == 0 ? 2 : 3);
            dp[ni] = max(dp[ni], dp[i] + es[i]);
        }

        // 答え算出
        int all = 0;
        for (int i = 0; i < w1.size(); i++) {
            all += w1[i];
        }
        for (int i = 0; i < w2.size(); i++) {
            all += w2[i];
        }
        return all - max(dp[m + 1], dp[m + 2]);
    }
};