洛谷 P1064 [NOIP 2006 提高组] 金明的预算方案

// ✗ P1064 的第一版：把「附件」这两个字当成背景，全当独立物品做一遍 01 背包。
//
// 这是绝大多数人真实的第一反应 —— 题面前半段全在讲家具，
// 「价格 × 重要度求和最大」看上去就是一道裸的 01 背包。
//
// ⚠ 它丢掉的正是这道题唯一的新东西：**买附件之前必须先买它的主件**。
// ★ 它算出来的答案恒 ≥ 正解（可行集变大了），而且官方样例一测就死（3500 vs 2200）。

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

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    vector<int> f(n / 10 + 1, 0);
    for (int i = 1; i <= m; i++) {
        int v, w, q;
        if (scanf("%d %d %d", &v, &w, &q) != 3) return 0;
        (void)q;                                    // ✗ 主件是谁？不管
        for (int j = n / 10; j >= v / 10; j--)
            f[j] = max(f[j], f[j - v / 10] + v * w);
    }
    printf("%d\n", f[n / 10]);
    return 0;
}

// P1064 [NOIP 2006 提高组] 金明的预算方案 —— ★ 这一版就能 AC。
//
// ★ 关键的一步：**它是分组背包，只是没写在脸上。**
//   一个主件和它的附件绑成**一组**，组内是四种互斥的买法：
//       ① 只买主件 ② 主件 + 附件1 ③ 主件 + 附件2 ④ 主件 + 两个附件
//   （题面写死了「每个主件可以有 0 个、1 个或 2 个附件」⇒ 组内最多就是这 4 种。）
//   然后就是第 25 章那三层循环：组 → 容量倒序 → 组内枚举。
//
// ⚠ 读入有一处不能想当然：题面**没有保证附件排在它的主件后面**，
//   所以要先把 m 件全读进来，再分两趟归组（见 p1064OnePass.cpp 那个反例）。
//
// ★ 「价格都是 10 元的整数倍」是题面发的一张许可证：钱数除以 10，规模缩 10 倍。

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

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    vector<int> v(m + 1), w(m + 1), q(m + 1);
    for (int i = 1; i <= m; i++)
        if (scanf("%d %d %d", &v[i], &w[i], &q[i]) != 3) return 0;

    n /= 10;                                        // ★ 许可证：价格都是 10 的倍数
    vector<vector<int>> att(m + 1);                 // att[主件] = 它的附件编号
    for (int i = 1; i <= m; i++) if (q[i] != 0) att[q[i]].push_back(i);

    // 每个主件一组，组内枚举「带哪几个附件」（0 ~ 2 个 ⇒ 最多 4 种）
    vector<int> f(n + 1, 0);
    for (int i = 1; i <= m; i++) {
        if (q[i] != 0) continue;                    // 附件不单独成组
        int cnt = (int)att[i].size();
        for (int j = n; j >= 0; j--)
            for (int s = 0; s < (1 << cnt); s++) {  // 组内那层，必须在最里面
                int cost = v[i] / 10, val = v[i] * w[i];
                for (int t = 0; t < cnt; t++)
                    if (s >> t & 1) {
                        int k = att[i][t];
                        cost += v[k] / 10; val += v[k] * w[k];
                    }
                if (cost <= j) f[j] = max(f[j], f[j - cost] + val);
            }
    }
    printf("%d\n", f[n]);
    return 0;
}

// ✗ P1064 的第二版：一边读一边归组 —— 假设了「附件一定排在它的主件后面」。
//
// 读到 `q = 0` 就新开一组，读到 `q > 0` 就直接挂到「第 q 件所在的那一组」上。
// 只要输入是「主件在前」，它就一点毛病都没有 —— 官方样例正好就是这样，所以样例放过它。
//
// ⚠ 而题面**从来没保证过这个顺序**（只说了 `qᵢ` 是它对应的主件，`0 ≤ qᵢ ≤ m`）。
// ★ 页面上量过：把输入的行序打乱，它当场就现形。
//   （这一版遇到「主件还没出现」的附件时直接把它丢掉 —— 行为是确定的，
//     不去读没初始化的东西，免得打出一个换台机器就变的数。）

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

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    vector<int> v(m + 1), w(m + 1);
    vector<vector<int>> att(m + 1);
    vector<int> mains;
    vector<char> seen(m + 1, 0);
    for (int i = 1; i <= m; i++) {
        int q;
        if (scanf("%d %d %d", &v[i], &w[i], &q) != 3) return 0;
        if (q == 0) { mains.push_back(i); seen[i] = 1; }
        else if (seen[q]) att[q].push_back(i);      // ✗ 主件还没读到？那就当这件不存在
    }

    int cap = n / 10;
    vector<int> f(cap + 1, 0);
    for (int i : mains) {
        int cnt = (int)att[i].size();
        for (int j = cap; j >= 0; j--)
            for (int s = 0; s < (1 << cnt); s++) {
                int cost = v[i] / 10, val = v[i] * w[i];
                for (int t = 0; t < cnt; t++)
                    if (s >> t & 1) { int k = att[i][t]; cost += v[k] / 10; val += v[k] * w[k]; }
                if (cost <= j) f[j] = max(f[j], f[j - cost] + val);
            }
    }
    printf("%d\n", f[cap]);
    return 0;
}