题目描述

小 A 准备了 $n$ 种食材用来制作料理，这些食材依次以 $1,2,\dots ,n$ 编号，第 $i$ 种食材的酸度为 $a_i$，甜度为 $b_i$。对于每种食材，小 A 可以选择将其放入料理，或者不放入料理。料理的酸度 $A$ 为放入食材的酸度之和，甜度 $B$ 为放入食材的甜度之和。如果料理的酸度和甜度相等，那么料理的调味是平衡的。

过于清淡的料理并不好吃，因此小 A 想在满足料理调味平衡的前提下，合理选择食材，最大化料理的酸度与甜度之和。你能帮他求出在调味平衡的前提下，料理酸度与甜度之和的最大值吗？

输入格式

第一行，一个正整数 $n$，表示食材种类数量。

接下来 $n$ 行，每行两个正整数 $a_i,b_i$，表示食材的酸度和甜度。

输出格式

输出共一行，一个整数，表示在调味平衡的前提下，料理酸度与甜度之和的最大值。

输入输出样例 #1

输入 #1

3
1 2
2 4
3 2

输出 #1

8

输入输出样例 #2

输入 #2

5
1 1
2 3
6 1
8 2
5 7

输出 #2

2

说明/提示

对于 $40\%$ 的测试点，保证 $1\le n\le 10$，$1\le a_i,b_i\le 10$。

对于另外 $20\%$ 的测试点，保证 $1\le n\le 50$，$1\le a_i,b_i\le 10$。

对于所有测试点，保证 $1\le n\le 100$，$1\le a_i,b_i\le 500$。

solution

动态规划，将 酸度 - 甜度 定义为不平衡度 x，f[x] 为 不平衡度为 x 时最大的酸度与甜度之和，然后用动态规划即可

代码

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "unordered_map"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"
#include "cstring"
#include "cmath"

using namespace std;

const int N = 1e5 + 5;

int n;

unordered_map<int, int> f[2]; // 不平衡度 => 最大和

int main() {
    cin >> n;
    int a, b, i;
    for (i = 1; i <= n; i++) {
        cin >> a >> b;

        f[i & 1] = f[i -  1 & 1];
        for (auto x: f[i - 1 & 1]) {
            f[i & 1][x.first + a - b] = max(f[i & 1][x.first + a - b], x.second + a + b);
        }

        f[i & 1][a - b] = max(f[i & 1][a - b], a + b);
    }
    cout << f[i - 1 & 1][0];

}

结果