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

题目传送门

思路

假设我们选取了

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

CPP

#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;
}

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

文章操作

题目传送门

思路

Code

相关推荐

评论

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