题解归档 - cf104118I

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118I
• 本地来源：problems/cf104118I/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/I
• 原始标题：Gym 104118I - Item Crafting

思路

Gym 104118I - Item Crafting

There are at most 15 final products and at most 10 raw materials.

Because every ingredient ID is larger than the item being crafted, the recipe graph is a DAG in decreasing ID order.

For every item, compute its raw-material requirement vector:

• raw material: one unit of itself;
• crafted item: sum of the requirement vectors of all ingredients.

Values are capped at stock + 1, because anything larger is simply impossible.

Then enumerate all subsets of the first n final products (2^15) and check whether the sum of their requirement vectors fits the available stocks.

Complexity: O((total recipe size) * raw + 2^n * raw), memory O(m * raw).

Checks:

• sample 1
• statement samples 2-4 reconstructed from PDF

代码

来源：problems/cf104118I/solution.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> recipe(m + 1);
    vector<int> raw_id(m + 1, -1);
    vector<int> stock;

    for (int i = 1; i <= m; ++i) {
        int c;
        cin >> c;
        if (c == 0) {
            int p;
            cin >> p;
            raw_id[i] = (int)stock.size();
            stock.push_back(p);
        } else {
            recipe[i].resize(c);
            for (int &x : recipe[i]) cin >> x;
        }
    }

    int r = (int)stock.size();
    vector<array<int, 10>> need(m + 1);
    for (auto &v : need) v.fill(0);

    for (int i = m; i >= 1; --i) {
        if (raw_id[i] != -1) {
            need[i][raw_id[i]] = 1;
        } else {
            for (int ing : recipe[i]) {
                for (int j = 0; j < r; ++j) {
                    int cap = stock[j] + 1;
                    need[i][j] = min(cap, need[i][j] + need[ing][j]);
                }
            }
        }
    }

    int total = 1 << n;
    vector<array<int, 10>> subset(total);
    for (auto &v : subset) v.fill(0);

    int ans = 0;
    for (int mask = 1; mask < total; ++mask) {
        int bit = mask & -mask;
        int id = __builtin_ctz(bit) + 1;
        subset[mask] = subset[mask ^ bit];
        bool ok = true;
        for (int j = 0; j < r; ++j) {
            int cap = stock[j] + 1;
            subset[mask][j] = min(cap, subset[mask][j] + need[id][j]);
            if (subset[mask][j] > stock[j]) ok = false;
        }
        if (ok) ans = max(ans, __builtin_popcount((unsigned)mask));
    }

    cout << ans << '\n';
    return 0;
}