洛谷 P1855 榨取kkksc03

// ✗ P1855 的第一版：贪心 —— 「先挑便宜的」。
//
// 这是绝大多数人真实的第一反应，而且它的理由听着很顺：
// 既然只数**件数**（每个愿望都值 1 分），那当然先做代价小的那些。
//
// ⚠ 问题在于「代价小」没有主语：这里有**两种**代价。
//   这一版把它们加起来当成一把尺子（`m + t` 升序），能塞就塞。
//
// ★ 它到底错多少，页面上量过：不是「经常错得离谱」，而是「偶尔错一点点」——
//   这正是这类上当最难自查的地方。

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

int main() {
    int n, M, T;
    if (scanf("%d %d %d", &n, &M, &T) != 3) return 0;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++)
        if (scanf("%d %d", &a[i].first, &a[i].second) != 2) return 0;

    sort(a.begin(), a.end(), [](const pair<int, int>& x, const pair<int, int>& y) {
        return x.first + x.second < y.first + y.second;   // 两种代价加起来当一把尺子
    });

    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (a[i].first <= M && a[i].second <= T) { M -= a[i].first; T -= a[i].second; cnt++; }
    printf("%d\n", cnt);
    return 0;
}

// ✗ P1855 的第二版：把两种费用**加起来**，退回一维背包。
//
// 想法是：「反正都是代价，`m + t` 一起算，容量就是 `M + T`」——
// 这样第 23 章那份一维 01 背包一个字都不用改。
//
// ⚠ 它错在**两个上限是各自独立的**：
//   `m` 花超了不能拿 `t` 的余额去垫。合并之后这堵墙就没了。
//
// ★ 它有一条能写下来的性质：**答案恒 ≥ 正解**（只会高估，绝不会低估）——
//   因为每一组合法方案在合并之后仍然合法（`Σm ≤ M` 且 `Σt ≤ T` ⇒ `Σ(m+t) ≤ M+T`），
//   而反过来不成立。页面上那张表就是拿这条对出来的。

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

int f[405];   // 容量 M + T ≤ 400

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

// P1855 榨取kkksc03 —— ★ 这一版就能 AC。
//
// 二维费用 01 背包的**裸题**：每个愿望要同时付「钱」和「时间」两种代价，
// 而**价值全是 1**（题目只问「最多实现几个」）。
//
// 所以第 25 章那句口诀原样搬过来，只是内层多了一维：
//     for 每个愿望
//         for j = M .. m[i]     ← 钱，倒序
//             for k = T .. t[i] ← 时间，倒序
//                 f[j][k] = max(f[j][k], f[j-m][k-t] + 1)
//
// ⚠ 两个容量维**都**要倒序 —— 只要有一维写成正序，同一个愿望就能被实现好几次
//   （见 p1855Up.cpp，那时候它解的是「每个愿望可以许愿无限次」那道题）。

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

int f[205][205];   // f[j][k] = 花掉不超过 j 元、k 分钟，最多实现几个愿望

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

// ✗ P1855 的错法（一）：**外层**（钱）那一维写成了正序。
//
// 第 25 章正文第 5 步证过：二维费用里**方向的决定权只在外层**。
// 外层一旦正序，`f[j-m][…]` 那一整行这一轮早就填完了 —— 同一个愿望可以被反复实现。
//
// ★ 而它不是「随便错」：它**精确地**解了「每个愿望可以实现无限次」那道题
//   （= p1855Full.cpp，300 轮逐组相等）。

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

int f[205][205];

int main() {
    int n, M, T;
    if (scanf("%d %d %d", &n, &M, &T) != 3) return 0;
    for (int i = 0; i < n; i++) {
        int m, t;
        if (scanf("%d %d", &m, &t) != 2) return 0;
        for (int j = m; j <= M; j++)              // ✗ 外层正序
            for (int k = T; k >= t; k--)          // 内层仍然倒序，救不回来
                f[j][k] = max(f[j][k], f[j - m][k - t] + 1);
    }
    printf("%d\n", f[M][T]);
    return 0;
}

// P1855：外层倒序、**内层正序** —— 第 25 章正文说过「内层怎么写都一样」。
//
// ★★★ 这一页要问的是：那句话在这道题上还成立吗？
//
// 正文那条论证有一个没写出来的前提：`j - m` 得**真的是另一行**。
// 而它成立的条件是 `m ≥ 1` —— 一旦某个愿望的**金钱费用是 0**，
// `f[j-0][k-t]` 读的就是**同一行**，内层方向立刻变成决定性的：
// 那个愿望会沿着时间轴被反复实现。
//
// ⚠ 而 P1855 的题面**根本没给 m、t 的下界**（只写了 `0 ≤ M ≤ 200`、`0 ≤ T ≤ 200`）。
// ⇒ 页面上那张表：照「m, t ≥ 1」随机 300 轮抓 **0** 次（结构性的 0，不是概率低）；
//    生成器加一档「允许 m = 0」，当场 300 / 300。

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

int f[205][205];

int main() {
    int n, M, T;
    if (scanf("%d %d %d", &n, &M, &T) != 3) return 0;
    for (int i = 0; i < n; i++) {
        int m, t;
        if (scanf("%d %d", &m, &t) != 2) return 0;
        for (int j = M; j >= m; j--)              // 外层倒序（对的）
            for (int k = t; k <= T; k++)          // 内层正序 —— 只有 m = 0 时才咬人
                f[j][k] = max(f[j][k], f[j - m][k - t] + 1);
    }
    printf("%d\n", f[M][T]);
    return 0;
}