P8268 [USACO22OPEN] Alchemy B 题解

· · 题解

在博客园阅读 在洛谷上阅读

Part 0 题意简述

原题

给出拥有的金属数量与金属配方，求金属 N 最大能合成的数量。

Part 1 题目分析

首先，金属 i 能配出的最大数量只和它的原数量和它的配方中能合成的数量有关。

所以我们应该能想到递归，可以使用一个 bool 类型的递归函数来返回合成是否可行：

  1. 如果有金属 i，返回可行并减去一份金属 i；
  2. 如果没有金属 i 且没有配方，则返回不可行；
  3. 如果没有金属 i 有配方就递归配方所需金属 r；
    1. 有任一不可行，返回不可行；
    2. 所有可行，返回可行。

Part 2 代码

根据上方分析，可以写出递归函数：

// vector<int> recipe[100+20];
bool dfs(int metal){
    if(a[metal]){ //情况 1
        a[metal]--;
        return 1;
    }
    if(recipe[metal].empty()) //情况 2
        return 0;
    for(auto it:recipe[metal]) //情况 3
        if(!dfs(it))
            return 0; //情况 3-1
    return 1; //情况 3-2
}

结合其他部分，写出完整代码：

#include<iostream>
#include<vector>
using namespace std;
const int MAXN=1e2+20;
vector<int> recipe[MAXN];
int n,k;
int l,m;
int a[MAXN],ans;
inline bool dfs(int metal){
    if(a[metal]){
        a[metal]--;
        return 1;
    }
    if(recipe[metal].empty())
        return 0;
    for(auto it:recipe[metal])
        if(!dfs(it))
            return 0;
    return 1;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cin>>k;
    while(k--){
        cin>>l>>m;
        while(m--){
            int metal;
            cin>>metal;
            recipe[l].push_back(metal);
        }
    }
    ans=a[n],a[n]=0;
    while(dfs(n))
        ans++;
    cout<<ans;
    return 0;
}

Part 3 对其他题解的 Hack

因为题目中没有保证配方金属按顺序排列，所以可以造出以下数据： 输入：

3
1 0 0
2
2 1 1
3 2 2 1

输出（正解）： 0

输出（错误）： 1

被 Hack 的题解： kbzcz 题解 dts_std 题解