（5.23更新）P8268题解
dts_std
2022-05-23 19:47:41
### 更新日志
upd on 2022.5.18：规范 $LeTeX$ 公式。
upd on 2022.5.23：修改小错误，再次规范版面，丰富后记内容。
[题目传送门](https://www.luogu.com.cn/problem/P8268)
### 题目大意
奶牛有 $n$ 种金属，第 $i$ 种金属有 $a_{i}$ 个。现在告诉你每种金属的数量和 $k$ 个合成表，问你最多合成多少个第 $n$ 种金属。
~~我怎么想到了MC中的工作台啊。。。~~
### 解法
话不多说，向上解法，再解释。
我用了递归解决本题。
先把原来就有的 $n$ 号金属拿去，然后考虑合成。遍历制作 $n$ 号金属的合成表，能做几个就做几个。如果哪个金属没有了，再看它的合成表，可以做的话就做**一个**（注意：只做一个！），能再做一个 $n$ 号就再做一个。如果还能再做一个，就继续做，以此类推。
那该如何判断能不能做呢？这就要用到深搜的思想了。如果 $n$ 号金属缺材料，那么就看缺的材料的合成表。如果还缺，就继续看；如果不缺，就做一个。如果缺的材料无法制作，那就做不下去了。这时就可以输出答案了。
### 对解法的解释（Q&A）
Q1：为什么要用递归？
A1：因为判断的时候类似（其实就是）深搜，用递归最方便。当然，用栈也可以。
Q2：为什么每次只做一个？一起做不香吗？
A2：~~因为不这样弄会WA。~~
我们来着重回答为什么会WA。
先看一个输入栗子：
```
3
2 0 0
2
3 2 1 2
2 1 1
```
简单解释一下：
奶牛有 $3$ 种金属，$1$ 金属有 $2$ 个，$2$ 金属有 $0$ 个，$3$ 金属有 $0$ 个
共 $2$ 个合成表，合成表为：
1. 一个 $1$ 金属和一个 $2$ 金属可以合成一个 $3$ 金属；
2. 一个 $1$ 金属可以合成一个$2$ 金属。
如果我们采用能做就全做的方式做金属的话，步骤是这样的：
1. 发现缺 $2$ 金属；
2. 把所有 $1$ 金属做成 $2$ 金属；
3. 误以为材料够做两个 $3$ ，于是输出了 $2$，~~高高兴兴地WA~~。
即使第三步加了个判断：
此时缺 $1$，而 $1$ 无法制作，误以为无法制作 $3$ ，于是输出 $0$，~~又高高兴兴地WA~~。
这下我们就可以知道这种方法的错误之处了。若采用一次做全部的策略，有可能把原来需要的材料全用掉，使其不满足条件，但少用一些可能可以制作，这就导致了误判。
若一个一个做金属，步骤就是这样的：
1. 发现缺 $2$ 金属；
2. 把一个 $1$ 金属做成 $2$ 金属；
3. 此时奶牛有 $1$ 个 $1$ 金属和 $1$ 个 $2$ 金属，把他们做成 $1$ 个 $3$ 金属；
4. 发现不能再做了，输出 $1$ 。
所以答案为 $1$。
我们可以从此看出，一个一个做金属，就可以少用原材料，把能做的情况全考虑到，若这时还不能做，那是真不能做了。
Q3：该算法时间复杂度多少？有更快的方法吗？
A3：举个最坏情况的栗子：
```
5
5 0 0 0 0
4
2 1 1
3 2 1 2
4 3 1 2 3
5 4 1 2 3 4
```
对于第 $i$ 种金属，最坏遍历它前面的 $i-1$ 块金属，又因为这是一个一个制作的，所以次数还和 $a_{i}$ 的最大值有关，时间复杂度为 $O \left (n^2 \cdot \max_{1\le i\le n} a_{i} \right )$。
若你们想要更快的方法，请看楼下的二分答案。
### 代码
~~我知道你们只看这个~~
其中 $a$ 数组表示现有金属数，$b$ 数组表示合成表，$dfs$ 函数的返回值表示是否能合成第 $k$ 个金属。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
long long a[110],b[110][110];
bool dfs(long long k){
if(a[k]>0) return true;
if(b[k][0]==0) return false;//当没有该种材料且无法合成它时，返回false
long long i;
for(i=b[k][0];i>=1;i--){/*这里一定要倒着扫，因为如果顺着扫，
后面dfs的过程中可能会用掉前面做好的材料，导致WA。若倒着扫，即使
后面的dfs用掉了前面的材料，前面还会再补上*/
if(!dfs(b[k][i])) return false;//无法合成
}
for(i=1;i<=b[k][0];i++){//如果能合成，做一个
a[b[k][i]]--;
}
a[k]++;
return true;
}
int main(){
long long n,k,i,j,t,ans=0;
scanf("%lld",&n);
for(i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
scanf("%lld",&k);
for(i=1;i<=k;i++){
scanf("%lld",&t);
scanf("%lld",&b[t][0]);
for(j=1;j<=b[t][0];j++){
scanf("%lld",&b[t][j]);
}
}
ans=a[n];a[n]=0;
while(dfs(n)){
ans++;
a[n]=0;
}
printf("%lld",ans);
return 0;
}
```
[AC记录](https://www.luogu.com.cn/record/75893019)
### 后记
尽管我觉得递归才是正解，但人家二分答案就是快。
引用一下我们老师说的名言：
空间复杂度是你竞争的底线，时间复杂度是你竞争的目标。
再引用一下洛谷上别人（忘了是谁）说的名言：
题解千万条，理解第一条。如果直接抄，棕名两行泪。