Loading [MathJax]/jax/output/CommonHTML/jax.js

每日一题:共鸣问题

题意

现在有 n 个音符和 m 对共鸣关系,编号为 1n,每个音符自己有一个奏响时的优美程度,共鸣关系 (x,y,z) 表示音符 xy 同时奏响的额外优美程度是 z,同时不奏响则为 z,其他情况为 0,求最大优美程度。(n,m[1,1e5])

思路

对于一对共鸣关系而言,在不选的情况下收益为 z,则选择一个的话,收益为 z+z=0,都选择的话为 z+2z=z。因此可以预先把每对关系的两个数都加上 z,刚开始我们是不选任何有联系的音符的,因此初值为 z,那么选择一个数就会加上 z,选择两个就会加上 2z,满足了之前所讨论的关系。答案初始化为所有关系都不选的情况,即 sum(z),然后只要贪心的选择对答案有正贡献的值就行了。

Code

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
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param n int整型
* @param m int整型
* @param a int整型vector
* @param b int整型vector<vector<>>
* @return long长整型
*/
long long wwork(int n, int m, vector<int>& a, vector<vector<int> >& b) {
// write code here
vector<long long> c;
long long res = 0;
for (auto& x : a) c.push_back(x);
for (auto& v : b) {
c[v[0] - 1] += v[2];
c[v[1] - 1] += v[2];
res -= v[2];
}
for (auto& x : c) res += max(x, 0);
return res;
}
};
作者

Benboby

发布于

2020-12-23

更新于

2021-01-28

许可协议

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×