Luogu P2036 [COCI2008-2009 #2] PERKET

Luogu P2036 [COCI2008-2009 #2] PERKET

#include <bits/stdc++.h>

using namespace std;

int n, ans = 1e9 + 5;  // ans初始化值大于所有可用食材全部使用产生的总酸度和总苦度

int s[15], b[15];

void dfs(int tot, int k, int l) {  // k为当前酸度，l为当前甜度
    if (tot > n) {
        if (k == 1 && l == 0) return ;  // 对水进行特判
        ans = min(ans, abs(k - l));
        return ;
    }
    dfs(tot + 1, k, l);  // 选择不加第tot份食材，继续枚举
    dfs(tot + 1, k * s[tot], l + b[tot]);  // 选择加第tot份食材，继续枚举
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i] >> b[i];
    dfs(1, 1, 0);  // 默认是水
    cout << ans << endl;
    return 0;
}