python/LuoGu/RuMen/P2036.cpp

#include <bits/stdc++.h>

using namespace std;

//https://www.luogu.com.cn/problem/P2036

//定义长长整为ll,用着方便
typedef long long ll;

//结构体:配料
struct ingredient {
    ll S;//酸度
    ll B;//甜度
} x[11]; //配料数最多是10个，就算是把0不要了，11个也足够了

int n;
ll ans = 10000001; //酸度和甜度的最小的绝对差
ll S_RESULT = 1; //酸度乘法结果
ll B_RESULT = 0; //甜度加法结果

//深度优先搜索
void dfs(int i) {
    //并不是到n停止，注意一下,要到4号小箱子啊！
    if (i == n + 1) {
        //如果一个都没选就不存最小值，否则会出现ans=0的情况
        if (S_RESULT == 1 && B_RESULT == 0) {
            return;
        }
        //本轮走到头与其它各轮次的结果对比，哪个小就保留哪个
        ans = min(ans, abs(S_RESULT - B_RESULT));
        return;
    }
    //如果本轮要x[i]这种配料
    S_RESULT *= x[i].S; //酸度乘法结果
    B_RESULT += x[i].B;  //甜度加法结果
    //探索下一个配料!
    dfs(i + 1);

    //如果本轮不要x[i]这种配料
    S_RESULT /= x[i].S;//回溯
    B_RESULT -= x[i].B;//回溯
    //直接跳到下一种配料
    dfs(i + 1);
}

int main() {
    //读入输出优化的强迫症
    ios::sync_with_stdio(false);
    //可支配的配料数
    cin >> n;
    //输入配料数据
    for (int i = 1; i <= n; i++)
        cin >> x[i].S >> x[i].B; //先酸度，后甜度
    //从第一个配料开始吧！
    dfs(1);

    //输出:酸度和甜度的最小的绝对差。
    cout << ans;
    return 0;
}