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

Part 0 题意简述原题

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

Part 1 题目分析

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

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

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

Part 2 代码

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

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

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

#include#includeusing namespace std;const int MAXN=1e2+20;vector 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>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

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

31 0 022 1 13 2 2 1

输出（正解）：
0

输出（错误）：
1

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