AtCoder题解｜XXOR

AtCoder题解｜ABC 117D XXOR

---

题目信息 📚

【题目描述】

There are $N$ gems. The value of the $i$-th gem is $V_i$.

You will choose some of these gems, possibly all or none, and get them.

However, you need to pay a cost of $C_i$ to get the $i$-th gem.

Let $X$ be the sum of the values of the gems obtained, and $Y$ be the sum of the costs paid.

Find the maximum possible value of $X - Y$.

【输入】

The input is given from Standard Input in the following format:

$N$

$V_1$ $V_2$ $\ldots$ $V_n$

$C_1$ $C_2$ $\ldots$ $C_n$

【输出】

Print the maximum possible value of $X - Y$.

【数据范围】

All values in the input are integers.

• $1 \leq N \leq 20$
• $1 \leq C_i, V_i \leq 50$

【输入样例1】

3
10 2 5
6 3 4

【输出样例1】

5

【输入样例2】

4
13 21 6 19
11 30 6 15		

【输出样例2】

6

【输入样例3】

1
1
50

【输出样例3】

0

【题目来源】

https://atcoder.jp/contests/abc125/tasks/abc125_b

---

题目解析 🍉

【题目分析】

由于数据范围较小，二进制枚举所有方案也就 $2^{20} \approx 10^6$ 级别，因此可以直接DFS暴搜。

当然，这题很容易和背包问题混淆起来，实际上并没有那么复杂：贪心，求 $X - Y$ 的最大值，只要当前物品的 $V_i > C_i$ 即可。

【C++代码】

DFS ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 60;
int n, c[N], v[N];
int res = 0;

// DFS暴搜
// step表示当前已经选到第step个物品，is_select表示是否选择第step个物品
// vsum表示当前V总和，csum表示当前C总和
void dfs(int step, int is_select, int vsum, int csum) {
    if (step == 21) {
        res = max(res, vsum - csum);
        return;
    }
    dfs(step + 1, 0, vsum, csum);
    dfs(step + 1, 1, vsum + v[step + 1], csum + c[step + 1]);

}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入数据
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) cin >> c[i];

    // 不选第1个物品
    dfs(1, 0, 0, 0);
    // 选择第1个物品
    dfs(1, 1, v[1], c[1]);

    cout << res << endl;

    return 0;
}

贪心 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 60;
int n, c[N], v[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入数据
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) cin >> c[i];

    // 贪心
    LL sum = 0;
    for (int i = 1; i <= n; i++) {
        if (v[i] > c[i]) sum += (v[i] - c[i]);
    }
    cout << sum << endl;

    return 0;
}