洛谷 P1616 疯狂的采药

// P1616 疯狂的采药 —— ★ 这一版就能 AC
//
// 题意：时间 t，m 种草药，第 i 种采一次要 a[i] 时间、值 b[i]；**每种可以无限次采**。
//       求能采到的最大总价值。
//
// ★ 它就是[第 23 章 P1048 采药](/sol/p1048/)的完全背包版 ——
//   两道题的代码只差**一个字**：内层循环的方向。
//     01 背包（每种一件）  ：for (j = t; j >= a; j--)
//     完全背包（每种无限） ：for (j = a; j <= t; j++)     ← 就是这一行
//   [第 24 章第 ⑧ 步](/ch/24-knapsack-multi/)把这件事讲透了：
//   正序之所以「错」在 01 背包里，正是因为它**恰好在解完全背包**。
//
// ⚠⚠ 而这道题真正咬人的地方在**数据范围那三行**（解析页第 ② ③ 步）：
//   ① `1 ≤ m × t ≤ 10^7` —— 出题人**直接把复杂度写在题面上了**：`O(mt)` 恒 ≤ 10^7。
//      （只看 `t ≤ 10^7` 和 `m ≤ 10^4` 会以为是 10^11，那就不敢写这个 DP 了。）
//   ② 答案会**超过 int**：`t = 10^7`、`a = 1`、`b = 10^4` ⇒ 答案 10^11。
//   ③ 而 `f` 数组有 `t+1` 格 ⇒ 顶格时 `long long` 要 **76 MB**（限制 128 MB，塞得下）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t, m;
    if (!(cin >> t >> m)) return 0;
    vector<long long> f(t + 1, 0);             // ⚠ long long：答案能到 10^11
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        for (int j = a; j <= t; j++)           // ★ 正序 —— 每种草药可以重复采
            f[j] = max(f[j], f[j - a] + b);
    }
    cout << f[t] << "\n";
    return 0;
}

// P1616 错法一：内层写成倒序 —— 它精确地解回了 01 背包
//
// 这是[第 24 章第 ⑧ 步](/ch/24-knapsack-multi/)那句话的反向现场：
// **完全背包写成倒序，输出恒等于同一组数据的 01 背包答案。**
// 解析页第 ④ 步把这句话量成了「300 组逐组相等」。
//
// ★ 官方样例当场挡住它：`t = 70`，三种草药 (71,100)(69,1)(1,2)
//   ⇒ 完全背包能把第三种采 70 次 = 140；而 01 背包每种只能采一次，
//     最好是 69 + 1 两株 = 1 + 2 = 3。差了 46 倍。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t, m;
    if (!(cin >> t >> m)) return 0;
    vector<long long> f(t + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        for (int j = t; j >= a; j--)           // ⚠ 倒序 —— 每种只采得了一次
            f[j] = max(f[j], f[j - a] + b);
    }
    cout << f[t] << "\n";
    return 0;
}

// P1616 错法三：性价比贪心 —— 一直采「单位时间价值最高」的那一种
//
// 完全背包里这个贪心比在 01 背包里**离对更近**：既然可以无限采，
// 那就一直采性价比最高的那种，剩下的零头再拿次高的补 —— 听起来很有道理。
//
// ⚠ 它仍然是错的，而且错的**方式**和 [P1048](/sol/p1048/) 不一样：
//   01 背包里它错在「一件也不能多拿」，这里它错在**凑不满最后那点零头**。
//   解析页第 ⑤ 步把三道题的同一个贪心并排量了一遍：
//     [P2240 部分背包](/sol/p2240/)（能切）—— **它是对的**；
//     [P1048 01 背包](/sol/p1048/)     —— 300 轮错 57 次，错时平均差 10.96%；
//     本题（完全背包）                  —— 见那一页的表。
//
// ★ 这里如实写成「按性价比排序，从高到低能采就一直采」。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t, m;
    if (!(cin >> t >> m)) return 0;
    vector<pair<int, int>> h(m);               // (a 时间, b 价值)
    for (auto& e : h) cin >> e.first >> e.second;

    sort(h.begin(), h.end(), [](const pair<int, int>& x, const pair<int, int>& y) {
        return (long long)x.second * y.first > (long long)y.second * x.first;   // b/a 从大到小
    });

    long long ans = 0;
    int left = t;
    for (auto& e : h) {
        long long cnt = left / e.first;
        ans += cnt * e.second;
        left -= (int)(cnt * e.first);
    }
    cout << ans << "\n";
    return 0;
}