Part 0 题意简述
原题
给出拥有的金属数量与金属配方,求金属 \(N\) 最大能合成的数量。
Part 1 题目分析
首先,金属 \(i\) 能配出的最大数量只和它的原数量和它的配方中能合成的数量有关。
所以我们应该能想到递归,可以使用一个 bool
类型的递归函数来返回合成是否可行:
- 如果有金属 \(i\),返回可行并减去一份金属 \(i\);
- 如果没有金属 \(i\) 且没有配方,则返回不可行
- 如果没有金属 \(i\) 有配方就递归配方所需金属 \(r\);
- 有任一不可行,返回不可行;
- 所有可行,返回可行。
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 题解
原文地址:http://www.cnblogs.com/WorldHim/p/solution-luogu-p8268.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性