在洛谷上閱讀 在博客園閱讀
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 題解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/514254.html
標籤：其他
上一篇：如何撰寫 Pipeline 腳本