【精進】ABC288 E - Wish List

どの$C$を使えるかが問題

問題

E - Wish List
$1,\dots,N$の番号がついた$N$個の商品がありそのうち$M$個の商品がほしい。商品$i$を買うためには、その時点で購入されていない商品の番号のうち$i$が小さい順に$j$番目だとすると $A_i+C_j$を払う必要がある。欲しい商品を全て買うために払う金額の最小値を求めよ。$N\le 5000$

解法

見た目的にも制約的にもDPを考えたくなる。$\text{dp} [i][j]$を$i$未満の欲しい商品をすべて買い、( $i$未満の商品の内 )$j$個の商品が買われていないときの購入金額の最小値とする。初め$\text{dp} [i][j] = \infty$で初期化しておき、遷移を考える。商品$i$が欲しい商品でない場合買うかどうかは任意であり、買わない場合の遷移は$\text{dp} [i+1][j] \xleftarrow{\min} \text{dp} [i][j-1]$である。商品$i$を購入する場合、商品$i$を購入するタイミングは$i$未満の商品の購入金額に影響を与えない。また$i$未満の商品を(最終的に)$j$個買わない場合、商品$i$購入時の$i$未満の未購入の商品の個数として考えられるのは$j,\dots,i$個である。従って遷移は

\[\text{dp} [i+1][j] \xleftarrow{\min} \text{dp} [i][j]+A_i+\min_{j\le k\le i}C_k\]

となる。$\min_{j\le k\le i}C_k$はセグ木で実装したが、$\log$をつけないこともできる。

#include "data_structure/segtree.hpp"
ll op(ll a, ll b) {
    return min(a, b);
}
ll e() {
    return inf;
}
void solve() {
    LL(n, m);
    vl a(n), c(n);
    vector<bool> x(n, false);
    input(a);
    input(c);
    segtree<ll, op, e> seg(c);
    rep(i, m) {
        LL(xi);
        x[--xi] = true;
    }
    Graph dp(n + 1, vl(n + 1, inf));
    dp[0][0] = 0;
    rep(i, n) {
        rep(j, n + 1) {
            if(j and !x[i]) {
                chmin(dp[i + 1][j], dp[i][j - 1]);
            }
            if(j != n and j <= i)
                chmin(dp[i + 1][j], dp[i][j] + a[i] + seg.prod(j, i + 1));
        }
    }
    print(*min_element(all(dp[n])));
}
int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
}