CF-1249 F.Maximum Weight Subset(貪心)

題目鏈接

題意

在一棵樹(shù)上選一些點(diǎn)構(gòu)成一個(gè)集合,滿足集合內(nèi)任意兩點(diǎn)的距離大于$k$,求集合的最大權(quán)值和

思路

一共200個(gè)點(diǎn),可以從最低層的點(diǎn)$u$開(kāi)始,默認(rèn)選擇這個(gè)點(diǎn),然后將它距離$k$的點(diǎn)權(quán)值減小$val[u]$表示這些點(diǎn)不選.

這樣向上找的時(shí)候如果碰到權(quán)值為正的點(diǎn),表示選擇這個(gè)點(diǎn)的權(quán)值更優(yōu),同時(shí)不會(huì)影響其他點(diǎn)

復(fù)雜度$O(n^2)$

#include <bits/stdc++.h> const int maxn = 1e5 + 5; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; vector<int> g[maxn]; int a[maxn], b[maxn], dep[maxn], n, k; void dfs(int u, int fa, int d) {dep[u] = d;for (auto v : g[u]) {if (fa == v) continue;dfs(v, u, d+1);} } void dfs(int u, int fa, int x, int d) {if (d > k) return;a[u] -= x;for (auto v : g[u]) {if (fa == v) continue;dfs(v, u, x, d+1);} } int main() {cin >> n >> k;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i < n; ++i) {int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, 0, 0);for (int i = 1; i <= n; ++i) b[i] = i;sort(b+1, b+1+n, [&](int x, int y){return dep[x] > dep[y];});int ans = 0;for (int i = 1; i <= n; ++i) {if (a[b[i]] <= 0) continue;ans += a[b[i]];dfs(b[i], 0, a[b[i]], 0);}cout << ans << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF-1249 F.Maximum Weight Subset(贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。