Doka Eating

2 secs 1024 MB

east1016

Problem

Submissions

Test cases

Editorial

基本方針

$100$ グラム $1$ 円のハンバーガーが常に存在することに着目します。

このハンバーガーの存在によって、 $1000$ 円以上のハンバーガーを注文する意味が完全になくなります。（重さが $\text{max}W = 10^5$ グラムだとしても $100$ グラム $1$ 円のハンバーガーの方がお得なので）

同じ値段のハンバーガーについては、重さが一番大きいものだけに選択肢を絞ることができます。

以上の考察を踏まえ、適切にハンバーガーを除外することで以下の制約の個数制限なしナップザック問題に帰着させることができます。

$1 \leq N \leq 1000$
$1 \leq M \leq 10^{5}$
$1 \leq C_i \leq 1000$
$1 \leq W_i \leq 10^{5}$

ここからの解説は以下の記事を参考にすると良いでしょう。

https://qiita.com/O-Jun/items/e9e411916efd3377c228

実装例(C++)

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
​
int main() {
    int n, m, mx = 1000;
    cin >> n >> m;
    vector<int> menu(mx);
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (a < mx) menu[a] = max(menu[a], b);
    }
    vector<int> w, c;
    for (int i = 0; i < mx; i++) {
        if (!menu[i]) continue;
        c.push_back(i);
        w.push_back(menu[i]);
    }
    vector<long long> dp(m + 1, 0);
    int sz = c.size();
    for (int i = 0; i < sz; i++) {
        for (int j = c[i]; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;
}
​