簡單DFS
直接上圖片
簡單思路
題目所給配料數 N 位于 0 到 10之間，果斷DFS列舉每一種情況，對于每種配料進行選與不選的判斷，直到列舉完所有情況，同時需要注意，不能一個配料都不選，所以在這里我選用了定義一個堆疊，在最后判斷堆疊是否為空的方式來判斷是否選擇了配料，
閑話不多說，直接上代碼，
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <stack> using namespace std; #define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int INF = 0x3f3f3f3f; typedef long long ll; struct cook { int acid; int sweet; }c[15]; int minChoose = INF; int n ; int sumAcid = 1; int sumSweet = 0; stack<cook> s; void dfs(int deep){ if(deep > n){//如果所有配料都判斷完了 if(abs(sumAcid - sumSweet) < minChoose && !s.empty()){ minChoose = abs(sumAcid - sumSweet); } return; } //選 sumAcid *= c[deep].acid; sumSweet += c[deep].sweet; s.push(c[deep]); dfs(deep + 1); //不選 sumAcid /= c[deep].acid; sumSweet -= c[deep].sweet; s.pop(); dfs(deep + 1); } int main() { fastio; cin >> n; for(int i = 1 ;i <= n;i++){ cin >> c[i].acid >> c[i].sweet; } dfs(1); cout << minChoose << endl; return 0; }點我看代碼>，<
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/17895.html
標籤：其他