AtCoder Beginner Contest 325F問題

ABC325F

解法

まず，素直に bool 型 dp を考える．

\( dp_{i,j,k} := \) 区間 \(i\) まで， センサー 1 を \(j\) 個， センサー 2 を \(k\) 個 で可能か
\(\in Bool\)

とする． 次に，bool 型 dp の定義域のいくつかを値域に移すことを考える． このとき，\(i,j\) は対象な条件なのでどちらでも良い．

値域に移すものは，何か良い性質を持っていないと，高速化は難しい． 定義域は全探索するので，綺麗な性質である必要が無い．

今回は，\(i,j\) を固定した前提で \(k\) は単調性があるので，値域に持っていくと高速化できる．

\(dp_{i,j} := \) 区間 \(i\) まで， センサー 1 を \(j\) 個 のときの \(k\) の min の合計
\(\in \mathbb{Z}\)

とする． 区間\(i\) について，\(j\) が決まれば，\(k\) の min が求まる． また，\(i\) に関しては，単調性などの綺麗な性質が見当たらないので， 値域に持って行っても高速化は難しい．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  vll d(n); rep(i,n) { cin >> d[i]; }

  vll l(2), c(2), k(2);

  rep(i,2) cin >> l[i] >> c[i] >> k[i];

  vll dp(k[0]+1, INFL);

  dp[0] = 0;

  rep(i,n){

    vll old(k[0]+1, INFL);

    swap(old,dp);

    rep(j,k[0]+1){

      // rep(add,k[0]+1)if(j+add <= k[0]){

      rep(add, k[0]+1-j){

        ll x = ceil(d[i] - add*l[0], l[1]);

        chmax(x, 0LL);

        chmin(dp[j+add], old[j] + x);

      }

    }

  }

  ll ans = INFL;

  rep(j,k[0]+1){

    if(dp[j] <= k[1]){

      chmin(ans, j*c[0] + dp[j]*c[1]);

    }

  }

  if(ans == INFL) ans = -1;

  cout << ans << endl;

  return 0;

}