問題概要

$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;
}

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

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

Codeforces 552 DIV3 F. Shovels Shop (R2300)

問題概要

制約

考えたこと