いかにも ABC-E にありあそうな DP！！

これとか似てる

問題概要

$N$ 個の店がある。 $D$ 日間にわたって、いずれか 1 つの店で買い物をする。

$d$ 日目に $i$ 番目の店で買い物をしたときの値段は $P_{d, i}$ で与えられる (10 の倍数)
ただし 2 日連続で同一の店で買い物をしたときは、1 割引きとなる
3 日以上連続で同一の店で買い物をしたときは、3 割引きとなる

$D$ 日間の買い物の支払い金額の総和の最小値を求めよ。

制約

$2 \le N \le 3000$
$1 \le D \le 365$

考えたこと

いかにも DP という感じ。次のような DP を考えたくなる

dp[ i ][ j ][ k ] := i 日間の買い物を行う。前日に買った店は j 番目であって、前日までに j 番目の店で k 回連続で買い物をしていたとする。この場合の総額の最小値

ただし、 $k$ の値は $0, 1, 2$ の 3 つで十分である。2 日連続以上となった場合はずっと $k = 2$ のままとすれば OK。

DP の遷移

前日にお店 j で買い物して、その次の日にお店 j2 で買い物をする場合を単純に探索 (以下のコードのように) すると、 $O(DN^{2})$ の計算量となってしまう。

for (int j = 0; j < N; ++j) {
    for (int k = 0; k < 3; ++k) {
        for (int j2 = 0; j2 < N; ++j2) {
            if (j != j2) chmin(dp[i+1][j2][1], dp[i][j][k] + (新しい価格));
            else chmin(dp[i+1][j2][min(k+1, 2)], dp[i][j][k] + (新しい価格));
        }
    }
}

もっと上手にできる。お店が変わる場合は、そもそも前日までのあらゆる場合の最小値を $m$ としたとき

for (int j = 0; j < N; ++j) chmin(dp[i+1][j][1], vmin + (新しい価格));

というふうに遷移すれば OK。お店が変わらない場合はそもそも j2 == j なので、新たな変数 j2 を持ち出す必要はない。

こうして計算量は $O(DN)$ となった。

コード

以下のコードでは、配列を使い回す実装をしている。

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (long long i = 0; i < (long long)(n); ++i)

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

const long long INF = 1LL<<60;
int main() {
    int N, D;
    cin >> N >> D;
    vector<vector<long long>> P(D, vector<long long>(N));
    REP(d, D) REP(i, N) cin >> P[d][i];

    vector<vector<long long>> dp(N, vector<long long>(3, INF));
    REP(j, N) dp[j][0] = 0;
    REP(d, D) {
        // DP の遷移先
        vector<vector<long long>> nex(N, vector<long long>(3, INF));

        // different item
        long long vmin = INF;
        REP(j, N) REP(k, 3) chmin(vmin, dp[j][k]);
        REP(j, N) chmin(nex[j][1], vmin + P[d][j]);

        // same item
        REP(j, N) REP(k, 3) {
            long long add = P[d][j];
            if (k == 1) add = add * 9 / 10;
            else if (k == 2) add = add * 7 / 10;
            chmin(nex[j][min(k+1, 2LL)], dp[j][k] + add);
        }

        // DP を遷移
        swap(dp, nex);
    }

    long long res = INF;
    REP(j, N) REP(k, 3) chmin(res, dp[j][k]);
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 春合宿 2008 day2-1 Nile.Com (難易度 6)

問題概要

制約

考えたこと

DP の遷移

コード