洛谷 P2925 [USACO08DEC] Hay For Sale S

// P2925 错法一：贪心 —— 体积从大到小，能装就装
//
// 和 [P1049](/sol/p1049/) 那个错法是同一个，错法也是同一个：
// **先把大的安顿好** ≠ **装得尽量满**。
//
// ★ 官方样例挡住了它：C = 7，三捆 2 / 6 / 5 ——
//   从大到小是 6、5、2 ⇒ 装 6（剩 1），5 和 2 都装不下 ⇒ 输出 6，而正解是 2 + 5 = 7。
//   ⇒ 这一次样例不客气。⚠ 而 P1049 的样例**放过了**同一个错法 ——
//     「样例挡不挡得住」的主语是那一组样例长什么样。

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

int main() {
    int c, h;
    if (!(cin >> c >> h)) return 0;
    vector<int> v(h);
    for (int& x : v) cin >> x;
    sort(v.begin(), v.end(), greater<int>());

    int left = c;
    for (int x : v) if (x <= left) left -= x;
    cout << c - left << "\n";
    return 0;
}

// P2925 [USACO08DEC] Hay For Sale S —— ★ 这一版就能 AC
//
// 题意：马车容量 C，H 捆稻草各有体积 Vi，不能拆开；问最多能装走多少体积。
//
// ★ 和 [P1049 装箱问题](/sol/p1049/) 是**同一道题的两种问法**：
//   那道问「剩余空间最小」，这道问「装走的体积最大」—— `答案 = C − 剩余`。
//   转化仍然是那一句：**只有体积没有价值 ⇒ 把体积当价值**（或者干脆记布尔可达）。
//
// ⚠⚠ 但这道题的数据范围和那道完全不是一个量级：
//   C ≤ 5 × 10^4、H ≤ 5 × 10^3 ⇒ O(HC) = 2.5 × 10^8。
//   ⇒ **二维表根本开不出来**（int 二维要 953 MB，而限制是 128 MB）。
//   ★ 而时间反倒不紧张：顶格最坏形状本机 71 毫秒，时限 1500 —— 余量 21 倍。
//     ⇒ 「压成一维」在这道题上**不是为了快，是为了开得出来**（解析页第 ③ 步）。
//
// ★ 这里记的是**布尔可达**（一个字节一格）而不是 int 表 —— ⚠ 而实测这一换**几乎不省时间**
//   （71 vs 78 毫秒，1.1 倍；两版内层次数一次不差）。真正快 24 倍的是 bitset。

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

const int MAXC = 50005;
char f[MAXC];                                  // f[j] = 「体积和恰好为 j」凑不凑得出来

int main() {
    int c, h;
    if (!(cin >> c >> h)) return 0;
    f[0] = 1;
    for (int i = 0; i < h; i++) {
        int v; cin >> v;
        for (int j = c; j >= v; j--)           // 倒序：每捆只能买一次
            if (f[j - v]) f[j] = 1;
    }
    for (int j = c; j >= 0; j--)
        if (f[j]) { cout << j << "\n"; break; }
    return 0;
}

// P2925 错法二：一维写成正序 —— 它精确地在解完全背包
//
// 正序 ⇒ 同一捆稻草可以被**买好几次**。于是它算出来的
// **恒等于「每捆稻草有无限多份」那道题的答案**（解析页第 ④ 步量成 300 组逐组相等）。
//
// ★ 在这道题上它有一个特别扎眼的后果：只要有一捆稻草的体积能整除某段空隙，
//   它就能把马车塞满 —— 而**只要有一捆体积为 1 的，它必定输出 C**。
//
// ⚠ 官方样例挡住了它：C = 7，2 / 6 / 5 ⇒ 正序能凑出 2+5 = 7 也能凑出别的，
//   输出仍是 7，和正解一样 —— ★ 不，样例**放过了它**（见解析页第 ④ 步那张表）。

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

const int MAXC = 50005;
char f[MAXC];

int main() {
    int c, h;
    if (!(cin >> c >> h)) return 0;
    f[0] = 1;
    for (int i = 0; i < h; i++) {
        int v; cin >> v;
        for (int j = v; j <= c; j++)           // ⚠ 正序
            if (f[j - v]) f[j] = 1;
    }
    for (int j = c; j >= 0; j--)
        if (f[j]) { cout << j << "\n"; break; }
    return 0;
}