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

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

Codeforces 552 DIV3 F. Shovels Shop (R2300)

問題概要

 N 個の品物があって、それぞれ価格は  a_1, a_2, \dots, a_N である。ここから  K 個の品物を何回かに買いたい。ここで一回の買い物につき一回ずつ使えるクーポン券が  M 個あって (使わなくても良い)、各クーポンは

  • ちょうど  x_i 個の品物を買ったならば、そのうちの安い順に  y_i 個の品物が無料になる

というサービスである。一回の買い物で使えるクーポンは一個だけだが、同じクーポンを何度でも使うことができる。さて、 K 個の品物を取り揃えるのに必要な最小コストを求めよ。

制約

  •  1 \le N, M \le 2 × 10^{5}
  •  1 \le K \le {\rm min}(N, 2000)

考えたこと

まずなんといっても、購入する  K 個の品物は安い順に  K 個で差し支えなさそう。そしてその  K 個のうち、クーポン効果で  0 円になる分を最大化する問題だと言える。

なんかこう、、、もし「どのクーポンから順に使っていけば良いか」が明確にわかるのであれば Greedy 感もなくはないのだけど、色々考えていると、a の値によってどのクーポンを適用するのがよいかもよくわからなくなるし、後に残るものがよいかもわからない。

こういうときは DP っぽい。今回同じクーポンを何度でも使って良いので、ちょうど区間をぶった切っていくような DP がぴったりである。

  • dp[ i ] := 最初の i 個買うときの購入する最小値

とする。 a のサイズは  K に限定されているので、計算量は  O(K^{2}) となる。

今週のお題「新生活おすすめグッズ」

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
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() {
    // a を小さい順に K 個とる
    int N, M, K; cin >> N >> M >> K;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a.begin(), a.end());
    a.resize(K);

    // a の累積和
    vector<long long> s(K+1, 0);
    for (int i = 0; i < K; ++i) s[i+1] = s[i] + a[i];
 
    // pa[v] := v 個買うときに pa[v] 個を 0 円にできる
    vector<int> pa(K+1, 0);
    for (int i = 0; i < M; ++i) {
        int x, y; cin >> x >> y;
        if (x > K) continue;
        chmax(pa[x], y);
    }

    // dp
    vector<long long> dp(K+1, 1LL<<60);
    dp[0] = 0;
    for (int i = 1; i <= K; ++i) {
        for (int j = 0; j < i; ++j) {
            int left = j + pa[i-j];
            chmin(dp[i], dp[j] + s[i] - s[left]);
        }
    }
    cout << dp[K] << endl;
}