ABC261 D

問題文⌗

N回のコイントスを行って、表が出たらお金がもらえます。しかし、表を出し続ければよいというわけではありません。この問題を難しくしているのが、連続で表を出すことによるボーナスです。なぜなら、例えば「2回連続表が出た場合」のボーナスがとても高い場合を考えます。このとき、10回連続表を出すよりも、裏を出してリセットし、先ほどのボーナスを取り続けたほうが儲かるかもしれません。コイントスを行って得たお金の最大値を求めるのがこの問題です。

解法⌗

結論から言うと、解法はdp(動的計画法、Dynamic Programming)です。 dpの特徴は、「前の計算結果を利用して次の結果を出す」ことです。 dpについて知らない方は、この記事を見ると分かりやすいかもしれないです。 dpを使うという判断の理由は、

前の計算からの結果が利用できそうである。
最適な行動をした場合の最大値を求める問題である。

などです。

さて、dpと言えば、考えるのはdpテーブルです。僕は以下のように定義しました。 $$ dp[i][j] = i番目のコイントスで、連続でj回表になっているとき、得られるお金の最大値。 $$ ただし、iは1-indexed。

次に考えるべきは、初期値と漸化式です。僕は次のように設定しました。

初期値 $dp[0][0] = 0$
表が出た場合 $dp[i+1][j+1] = \max(dp[i+1][j+1], dp[i][j] + X[i] + bonus[j+1])$
裏が出た場合 $dp[i+1][0] = \max(dp[i+1][0], dp[i][j])$

ただし、bonus[j]は、j回連続表が出た時のボーナス(ボーナスが出ない時は0)。

答えは、次のように選べばよいです。 $$ ans = \max_{0 \le j \le n}(dp[n][j]) $$

よって、$O(N^2)$でこの問題が解けました。 $1 \le n \le 5000$より、十分間に合います。

僕が提出したコードは以下です。

#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i < (n); i++)
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(void) {
    int n, m;
    cin >> n >> m;

    vector<int> x(n);
    rep(i, n) cin >> x[i];

    vector<vector<ll>> dp(5500, vector<ll>(5500, -1));

    map<ll, ll> bonus;
    rep(i, m) {
        ll ci, yi;
        cin >> ci >> yi;
        bonus[ci] = yi;
    }

    dp[0][0] = 0;
    rep(i, n) {
        rep(j, 5500) {
            if(dp[i][j] == -1) continue;
            chmax(dp[i + 1][0], dp[i][j]);
            chmax(dp[i + 1][j + 1], dp[i][j] + x[i] + bonus[j + 1]);
        }
    }

    ll ans = 0;
    rep(j, 5500) {
        chmax(ans, dp[n][j]);
    }

    cout << ans << endl;
    return 0;
}

5500という値は僕が「nの上限が5000だから適当に5500でループすればええやろ」と思って書いた値です。適宜、nやn+1に変えてもらえればより綺麗な解答になると思います。

余談⌗

dpを書くとき、$dp[i][j] = \max(dp[i][j], \ldots)$という式を書かなければなりません。しかし、少し冗長です。そこで、僕はそれをシンプルに書けるchminとchmaxという関数をテンプレートとして持っています。参考

実装は以下です。

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

知らなかった方はコピペして使ってみてはいかがでしょうか。

ABC261 D

目次

問題文⌗

解法⌗

余談⌗