题解：P13018 [GESP202506 七级] 调味平衡

A7F3jK9pR0xf_ · 2025-07-01 20:03:54 · 题解

题目传送门

思路

假设我们选取了 k 个物品，选取的第 i 个物品编号为 p_i，并且它们是“平衡”的，那么显然的性质：\sum_{i=1}^k(a_{p_i}-b_{p_i})=0。那么我们就可以将 a_i-b_i 当做重量，a_i+b_i 当做价值，进行 01 背包。由于可能有负数下标，使用 map 维护 dp 数组即可，注意转移细节。时间复杂度 O(nV\log nV)，其中 V 是值域，可理解为 10^5，\log 是 map 贡献的，可以通过此题。

Code

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define pi pair<int, int>
#define mkp make_pair
const int N = 110, M = 5e4 + 10;
map<int, int> dp[N];
int v[N], w[N];
int main()
{
    int n, a, b;
    cin >> n;
    dp[0][0] = 0;
    for(int i = 1;i <= n;++i)
    {
        cin >> a >> b;
        v[i] = a + b;
        w[i] = a - b;
        for(auto j : dp[i - 1])
        {
            dp[i][j.first] = max(dp[i][j.first], j.second);
            dp[i][j.first + w[i]] = max(dp[i][j.first + w[i]], j.second + v[i]);
        }
    }
    cout << dp[n][0];
    return 0;
}