Alchemy

题意

有 N 种金属，初始拥有金属 i 的数量为 a_i。

每个配方可以消耗若干种较小编号金属各 1 单位，制造 1 单位较大编号金属。每种金属最多只有一个制造它的配方。

求最终最多能拥有多少单位金属 N。

思路

先看一个小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:32
 * update_at: 2026-07-11 17:33
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;

int n, k;
int start_have[MAXN];
int recipe_cnt[MAXN];
int ingredient[MAXN][MAXN];
int best_answer;

bool recipe_available(int target, int have[]) {
    if (recipe_cnt[target] == 0) {
        return false;
    }
    for (int i = 1; i <= recipe_cnt[target]; i++) {
        int y = ingredient[target][i];
        if (have[y] <= 0) {
            return false;
        }
    }
    return true;
}

void apply_recipe(int target, int have[], int delta) {
    for (int i = 1; i <= recipe_cnt[target]; i++) {
        int y = ingredient[target][i];
        have[y] -= delta;
    }
    have[target] += delta;
}

// 枚举下一步执行哪个当前可用配方。
void dfs_convert(int have[]) {
    if (have[n] > best_answer) {
        best_answer = have[n];
    }

    for (int target = 1; target <= n; target++) {
        if (!recipe_available(target, have)) {
            continue;
        }

        apply_recipe(target, have, 1);
        dfs_convert(have);
        apply_recipe(target, have, -1);
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> start_have[i];
    }

    cin >> k;
    for (int i = 1; i <= k; i++) {
        int target, m;
        cin >> target >> m;
        recipe_cnt[target] = m;
        for (int j = 1; j <= m; j++) {
            cin >> ingredient[target][j];
        }
    }

    best_answer = start_have[n];
    int have[MAXN];
    for (int i = 1; i <= n; i++) {
        have[i] = start_have[i];
    }

    dfs_convert(have);

    cout << best_answer << '\n';

    return 0;
}

这个暴力每一步枚举当前能执行的配方，执行后继续搜索，记录金属 N 的最大数量。它能直接模拟题意，但配方执行顺序很多，只适合小数据。

满分做法从目标金属反向考虑。

如果想获得 1 单位金属 x：

如果当前已经有金属 x，直接消耗 1 单位；
否则只能使用制造 x 的配方；
如果没有这样的配方，就失败；
如果有配方，就递归制造配方需要的每个原料金属。

为什么这样可以？因为每种金属最多只有一个配方，不存在“选择哪种配方更优”的问题；并且配方只会从小编号金属制造大编号金属，递归不会成环。

于是写 can_make(x) 判断当前库存下能否获得 1 单位金属 x。主程序不断尝试：

text

1
2while can_make(N):
    answer += 1

第一次失败时，说明剩余库存已经无法再制造新的金属 N。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:32
 * update_at: 2026-07-11 17:33
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, k;
int have_metal[MAXN];       // 当前拥有的金属数量
int recipe_cnt[MAXN];       // recipe_cnt[x] 表示制造金属 x 需要几种原料金属
int ingredient[MAXN][MAXN]; // ingredient[x][i] 表示制造 x 的第 i 个原料

bool can_make(int x) {
    if (have_metal[x] > 0) {
        have_metal[x]--;
        return true;
    }

    if (recipe_cnt[x] == 0) {
        return false;
    }

    // 配方只依赖更小编号金属，所以递归不会成环。
    for (int i = 1; i <= recipe_cnt[x]; i++) {
        int y = ingredient[x][i];
        if (!can_make(y)) {
            return false;
        }
    }

    return true;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> have_metal[i];
    }

    cin >> k;
    for (int i = 1; i <= k; i++) {
        int target, m;
        cin >> target >> m;
        recipe_cnt[target] = m;
        for (int j = 1; j <= m; j++) {
            cin >> ingredient[target][j];
        }
    }

    int ans = 0;
    while (can_make(n)) {
        ans++;
    }

    cout << ans << '\n';

    return 0;
}

复杂度

按官方估计，时间复杂度为 $O(N^2 \cdot \max a_i)$ 。

空间复杂度为 $O(N^2)$ 。

总结

本题利用了“配方只从小编号指向大编号”这个无环结构。

目标不是枚举所有转换顺序，而是每次递归判断能否再造 1 单位金属 N。有库存就用库存，没有库存就按唯一配方继续向下要原料。

目录

题意

思路

代码

复杂度

总结