mayoko’s diary

プロコンとかいろいろ。

SRM 565 div1 easy MonstersValley

院試が終わりました。受かったらそれについてもなんか書きます。

問題

TopCoder Statistics - Problem Statement

0 ~ N-1 番までの商品を順番に買っていく。それぞれの商品には値段と重さがあり, 値段は 1 か 2 である。
あなたは, 今までに買った商品の重さの合計が今見ている商品の重さより小さい場合, その商品を買わなければならない。

最小でいくらの値段で N-1 番目までの商品を見終えることができるか。

解法

重さはかなり大きいので dp[i][w] = (i 番目までで合計 w の重さになったときの最小消費) という dp は無理です。ですが値段が 1 or 2 であることを利用して, dp[i][v] = (i 番目までで合計 v のお金を消費した時に得られる最大重量) という dp にすれば計算できます。

const int MAXN = 55;
ll dp[MAXN][2*MAXN];

class MonstersValley {
public:
    int minimumPrice(vector<long long> dread, vector <int> price) {
        int n = dread.size();
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 2*i; j++) if (dp[i][j] >= 0) {
                // 選ぶ
                dp[i+1][j+price[i]] = max(dp[i+1][j+price[i]], dp[i][j] + dread[i]);
                // 選ばない
                if (dp[i][j] >= dread[i]) {
                    dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
                }
            }
        }
        for (int i = 0; i <= 2*n; i++) {
            if (dp[n][i] >= 0) return i;
        }
        return -1;
    }
};