洛谷 P1507 NASA的食物计划

// ✗ P1507 的第一版：性价比贪心。
//
// 「每单位代价能换多少卡路里」听起来天经地义 —— 这一版按 `k / (h + t)` 从大到小排，
// 能装就装。它是[第 20 章 P1048](/sol/p1048/) 那个上当的**二维版本**。
//
// ⚠ 两处一起错：
//   ① 分母把两种代价加起来 —— 而这两个上限是各自独立的；
//   ② 就算只有一维，01 背包的性价比贪心本来就不对（不能切）。
//
// ★ 页面上量过：它的形状和 P1048 一模一样 ——**不是经常错得离谱，是偶尔错一点点**。

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

struct Item { int h, t, k; };

int main() {
    int H, T, n;
    if (scanf("%d %d", &H, &T) != 2) return 0;
    if (scanf("%d", &n) != 1) return 0;
    vector<Item> a(n);
    for (int i = 0; i < n; i++)
        if (scanf("%d %d %d", &a[i].h, &a[i].t, &a[i].k) != 3) return 0;

    sort(a.begin(), a.end(), [](const Item& x, const Item& y) {
        // 交叉相乘，避开浮点（分母可能是 0：体积和质量都为 0 的食品）
        return (long long)x.k * (y.h + y.t) > (long long)y.k * (x.h + x.t);
    });

    long long sum = 0;
    for (auto& it : a)
        if (it.h <= H && it.t <= T) { H -= it.h; T -= it.t; sum += it.k; }
    printf("%lld\n", sum);
    return 0;
}

// ✗ P1507 的第二版：只盯着体积，把质量那一维忘了。
//
// 这是「二维费用」题最典型的漏法 —— 题面里两个上限并排写着，
// 而代码里只有一个 `for j = H .. h[i]`。
//
// ★ 它有一条能写下来的性质：**答案恒 ≥ 正解**（少了一堵墙，可行集只会变大）。
//   ⇒ 它交上去是「答案偏大」的 WA，而且**它给出的那个方案往往是超重的**。

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

int f[405];

int main() {
    int H, T, n;
    if (scanf("%d %d", &H, &T) != 2) return 0;
    if (scanf("%d", &n) != 1) return 0;
    (void)T;                                   // ✗ 质量读进来了，然后再也没用过
    for (int i = 0; i < n; i++) {
        int h, t, k;
        if (scanf("%d %d %d", &h, &t, &k) != 3) return 0;
        (void)t;
        for (int j = H; j >= h; j--)
            f[j] = max(f[j], f[j - h] + k);
    }
    printf("%d\n", f[H]);
    return 0;
}

// P1507 NASA的食物计划 —— ★ 这一版就能 AC。
//
// 和同一章的 [P1855](/sol/p1855/) 是**同一道题**，只换了一处：
// 那道题「每个愿望都值 1 分」（只数件数），这道题每件食品有自己的卡路里。
// ⇒ 状态转移里那个 `+ 1` 换成 `+ k[i]`，别的一个字都不用改。
//
//     for 每件食品 i
//         for j = H .. h[i]      ← 体积，倒序
//             for l = T .. t[i]  ← 质量，倒序
//                 f[j][l] = max(f[j][l], f[j-h][l-t] + k)
//
// ⚠ 输入格式是三段：第一行 H T，第二行 n，再往下每行三个数 —— 顺序是**体积、质量、卡路里**。

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

int f[405][405];   // f[j][l] = 体积不超过 j、质量不超过 l 时的最大卡路里

int main() {
    int H, T, n;
    if (scanf("%d %d", &H, &T) != 2) return 0;
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n; i++) {
        int h, t, k;
        if (scanf("%d %d %d", &h, &t, &k) != 3) return 0;
        for (int j = H; j >= h; j--)
            for (int l = T; l >= t; l--)
                f[j][l] = max(f[j][l], f[j - h][l - t] + k);
    }
    printf("%d\n", f[H][T]);
    return 0;
}

// ✗ P1507 的第三版：把「体积」和「质量」这两列读反了。
//
// 输入格式那三行读起来很顺，可**每行三个数的顺序**是要一个字一个字对的：
//     第一行 H T      ← 体积上限、质量上限
//     每件食品 h t k  ← 体积、质量、卡路里
// 这一版把每件食品的前两个数读成了「质量、体积」，而两个上限没跟着换。
//
// ★ 页面上量过：它**不是一定错** —— 只有当两个上限（或两列费用）真的不对称时才会现形。

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

int f[405][405];

int main() {
    int H, T, n;
    if (scanf("%d %d", &H, &T) != 2) return 0;
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n; i++) {
        int h, t, k;
        if (scanf("%d %d %d", &t, &h, &k) != 3) return 0;   // ✗ 前两列读反了
        for (int j = H; j >= h; j--)
            for (int l = T; l >= t; l--)
                f[j][l] = max(f[j][l], f[j - h][l - t] + k);
    }
    printf("%d\n", f[H][T]);
    return 0;
}