P2036. PERKET

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 227 阅读时长 ≈ 1 分钟

考点

  • DFS

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>

using namespace std;

struct node
{
    int sour_, bitter_;
} arr[10];

int ans = INT_MAX, N;

void dfs(int idx, int sum_sour, int sum_bitter)
{
    if (sum_sour != 1 && sum_bitter != 0)
        ans = min(ans, abs(sum_sour - sum_bitter));
    if (idx == N)
        return;
    dfs(idx + 1, sum_sour, sum_bitter);
    dfs(idx + 1, sum_sour * arr[idx].sour_, sum_bitter + arr[idx].bitter_);
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> arr[i].sour_ >> arr[i].bitter_;
    dfs(0, 1, 0);
    cout << ans;
    return 0;
}

思路

每种配料都有选与不选两种情况，且最多只有10个配料，即210的复杂度，可以直接暴力DFS

题目说至少选一种配料，且酸度和苦度不同时为1和0

也就是说，只有初始状态，和所有配料都没选这两种特殊情况才有可能出现酸度为1且苦度为0

所以直接屏蔽酸度为1且苦度为0时的情况即可

1
2
if (sum_sour != 1 && sum_bitter != 0)
        ans = min(ans, abs(sum_sour - sum_bitter));