洛谷 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 题解