（5.23更新）P8268题解

dts_std · 2022-05-23 19:47:41 · 题解

更新日志

upd on 2022.5.18：规范 LeTeX 公式。

upd on 2022.5.23：修改小错误，再次规范版面，丰富后记内容。

题目传送门

题目大意

奶牛有 n 种金属，第 i 种金属有 a_{i} 个。现在告诉你每种金属的数量和 k 个合成表，问你最多合成多少个第 n 种金属。

~~我怎么想到了MC中的工作台啊。。。~~

解法

话不多说，向上解法，再解释。

我用了递归解决本题。

先把原来就有的 n 号金属拿去，然后考虑合成。遍历制作 n 号金属的合成表，能做几个就做几个。如果哪个金属没有了，再看它的合成表，可以做的话就做一个（注意：只做一个！），能再做一个 n 号就再做一个。如果还能再做一个，就继续做，以此类推。

那该如何判断能不能做呢？这就要用到深搜的思想了。如果 n 号金属缺材料，那么就看缺的材料的合成表。如果还缺，就继续看；如果不缺，就做一个。如果缺的材料无法制作，那就做不下去了。这时就可以输出答案了。

对解法的解释（Q&A）

Q1：为什么要用递归？

A1：因为判断的时候类似（其实就是）深搜，用递归最方便。当然，用栈也可以。

Q2：为什么每次只做一个？一起做不香吗？

A2：~~因为不这样弄会WA。~~

我们来着重回答为什么会WA。

先看一个输入栗子：

简单解释一下：

奶牛有 3 种金属，1 金属有 2 个，2 金属有 0 个，3 金属有 0 个

共 2 个合成表，合成表为：

一个 1 金属和一个 2 金属可以合成一个 3 金属；
一个 1 金属可以合成一个2 金属。

如果我们采用能做就全做的方式做金属的话，步骤是这样的：

发现缺 2 金属；
把所有 1 金属做成 2 金属；
误以为材料够做两个 3 ，于是输出了 2，~~高高兴兴地WA~~。

即使第三步加了个判断：

此时缺 1，而 1 无法制作，误以为无法制作 3 ，于是输出 0，~~又高高兴兴地WA~~。

这下我们就可以知道这种方法的错误之处了。若采用一次做全部的策略，有可能把原来需要的材料全用掉，使其不满足条件，但少用一些可能可以制作，这就导致了误判。

若一个一个做金属，步骤就是这样的：

发现缺 2 金属；
把一个 1 金属做成 2 金属；
此时奶牛有 1 个 1 金属和 1 个 2 金属，把他们做成 1 个 3 金属；
发现不能再做了，输出 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 个金属。

#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记录

后记

尽管我觉得递归才是正解，但人家二分答案就是快。

引用一下我们老师说的名言：

空间复杂度是你竞争的底线，时间复杂度是你竞争的目标。

再引用一下洛谷上别人（忘了是谁）说的名言：

题解千万条，理解第一条。如果直接抄，棕名两行泪。