今日の精進-DP（AtCoder ABC258-D）

今日、解き直した問題は AtCoder ABC258-D「Trophy」です。何回挑戦してもなかなかスッとACできないので、ポイントを整理しておきます。

問題

D - Trophy

ポイント

・1番目のステージ（A+B）を1回クリアして、残りX-1回は1番目のゲーム(B)でクリアする。
・2番目までのステージを1回ずつクリアして、残りX-2回は1、2番目の中から小さい方でクリアする。
・3番目までのステージを1回ずつクリアして、残りX-3回は1〜3番目の中から一番小さいものでクリアする。
　...（略）…
・N番目までのステージを1回ずつクリアして、残りX-N回は1〜N番目の中から一番小さいものでクリアする。
以上を全部試したときの最小値が答え。

ACしたコード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
const ll INF = 1LL << 62;
// const int INF = 1001001001;

int main() {
  int N;
  ll X;
  cin >> N >> X;

  vector<ll> A(N);
  vector<ll> B(N);
  vector<ll> sum(N);
  rep(i, N) {
    cin >> A[i] >> B[i];
    if (i == 0) {
      sum[i] = A[i] + B[i];
    } else {
      sum[i] = sum[i-1] + A[i] + B[i];
    }
  }

  ll ans = INF;
  set<ll> st;
  rep(i, N) {
    st.insert(B[i]);
    ll mn = *st.begin();
    ll res = sum[i] + mn * (X - (i+1));
    ans = min(ans, res);
  }

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

提出 #49993727 - AtCoder Daily Training MEDIUM 2023/10/18 18:00start

次回はスッとACできるようにしたい。