洛谷 P2347 [NOIP 1996 提高组] 砝码称重

// P2347 [NOIP 1996 提高组] 砝码称重 —— ★ 这一版就能 AC
//
// 题意：1g / 2g / 3g / 5g / 10g / 20g 六种砝码各若干枚（**总重 ≤ 1000**），
//       问能称出多少种不同的重量（**不包括一枚也不用的情况**）。
//
// ★ 它是**布尔版的多重背包**：状态不是「最大价值」而是「能不能凑出」。
//     f[j] |= f[j - 单堆重量]
//   转移里的 max 换成了「或」，其余和[第 24 章](/ch/24-knapsack-multi/)一模一样。
//
// ★ 而这道题在题单里的位置是「**拿来验证拆完答案不变**」：
//   总重 ≤ 1000 ⇒ 摊开也只有 10^6 次，拆不拆都能过。
//   ⇒ 所以它是个安全的地方，可以把「二进制拆分到底改没改答案」这件事**真验一遍**
//     （解析页第 ② 步：三种写法 300 组逐字节相同）。
//
// ⚠ 两个和算法无关、但一定要看清的地方：
//   ① 输出是 `Total=N`，**等号两边没有空格**；
//   ② 「不包括一个砝码也不用的情况」⇒ 答案是「可达重量数 **减 1**」（把 0 去掉）。

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

int main() {
    const int W[6] = { 1, 2, 3, 5, 10, 20 };
    const int MAXW = 1000;
    vector<char> f(MAXW + 1, 0);
    f[0] = 1;                                  // 一枚不用，重量 0

    for (int i = 0; i < 6; i++) {
        int a; if (!(cin >> a)) return 0;
        for (int k = 1; a > 0; k <<= 1) {      // ★ 二进制拆分
            int take = min(k, a);
            a -= take;
            int cw = W[i] * take;
            if (cw > MAXW) continue;
            for (int j = MAXW; j >= cw; j--)   // 倒序：这一堆只用一次
                if (f[j - cw]) f[j] = 1;
        }
    }

    int cnt = 0;
    for (int j = 1; j <= MAXW; j++) cnt += f[j];   // ⚠ 从 1 开始 —— 去掉「一枚不用」
    printf("Total=%d\n", cnt);                     // ⚠ 等号两边没有空格
    return 0;
}

// P2347 错法二：把「一枚砝码也不用」也数进去了
//
// 题面在输出格式那行明写着「**但不包括一个砝码也不用的情况**」。
// 这一版从 j = 0 开始数。
//
// ★ 它有一条白送的等式：**它的答案恒等于正解 + 1**（解析页第 ④ 步，300 / 300 逐组相等）。
//   ⇒ 说清楚之后，它的所有表现都是推论：任何一组数据它都错，而且永远只差 1。
//   ⇒ 于是它必然**被官方样例挡住**（Total=4 vs Total=3）——
//     又一次「[样例挡住的都是「每组都错」的](/sol/p1223/)」。

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

int main() {
    const int W[6] = { 1, 2, 3, 5, 10, 20 };
    const int MAXW = 1000;
    vector<char> f(MAXW + 1, 0);
    f[0] = 1;

    for (int i = 0; i < 6; i++) {
        int a; if (!(cin >> a)) return 0;
        for (int k = 1; a > 0; k <<= 1) {
            int take = min(k, a);
            a -= take;
            int cw = W[i] * take;
            if (cw > MAXW) continue;
            for (int j = MAXW; j >= cw; j--)
                if (f[j - cw]) f[j] = 1;
        }
    }

    int cnt = 0;
    for (int j = 0; j <= MAXW; j++) cnt += f[j];   // ⚠ 从 0 开始
    printf("Total=%d\n", cnt);
    return 0;
}

// P2347 错法三：算得全对，输出格式写成了 `Total = N`
//
// 题面写的是 `Total=N` —— **等号两边没有空格**。
// 而「Total = 3」看着更顺眼，很多人就顺手加了两个空格。
//
// ★★ 这一版的意义是提醒一件事：**对拍比对的时候不要 strip、不要按空白切词** ——
//   [第 10 章 P1068 那天踩过](/sol/p1068/)：自己那一轮 300 轮全绿，
//   而逐字节比报了 307 轮不一致。
//   ⇒ 这一类错**只有逐字节比才抓得到**，而它在评测机上是实打实的 0 分。

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

int main() {
    const int W[6] = { 1, 2, 3, 5, 10, 20 };
    const int MAXW = 1000;
    vector<char> f(MAXW + 1, 0);
    f[0] = 1;

    for (int i = 0; i < 6; i++) {
        int a; if (!(cin >> a)) return 0;
        for (int k = 1; a > 0; k <<= 1) {
            int take = min(k, a);
            a -= take;
            int cw = W[i] * take;
            if (cw > MAXW) continue;
            for (int j = MAXW; j >= cw; j--)
                if (f[j - cw]) f[j] = 1;
        }
    }

    int cnt = 0;
    for (int j = 1; j <= MAXW; j++) cnt += f[j];
    printf("Total = %d\n", cnt);                   // ⚠ 多了两个空格
    return 0;
}