【树形DP】Gym101667A Broadcast Stations

Souce:2017-2018 ACM-ICPC, Asia Daejeon Regional Contest
Problem:
一棵5e3的树，可以选择一些点放上基站，如果u上的基站价值为d，那么距离u小于等于d的点都会被覆盖，问使得整棵树被覆盖的最小价值。
Idea：
$g[u][j]$表示u点这颗子树里距离u点大于j的点都被覆盖的最小价值。
显然$g[u][j]=\sum g[v][j-1](j>0)$
$f[u][j]$表示将u点这颗子树全覆盖，并且这颗子树外距离u点小于等于d的点都被覆盖的最小价值。那么要么由子树传递，要么自己放上价值为j的基站。
$f[u][j]=min(f[v][j+1]-g[v][j],j)+g[u][j+1]$
最后得到$g[u][0]=f[u][0]$
Code:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 5e3+10;
const int INF = 0x3f3f3f3f;
int n, f[N][N], g[N][N];
vector<int> G[N];
void dfs(int u, int fa) {
for(int v:G[u]) if(v != fa) {
dfs(v, u);
for(int i = 1; i <= n; i++) g[u][i] += g[v][i-1];
}
g[u][0] = n; f[u][n] = n;
for(int i = n-1; i >= 0; i--) {
f[u][i] = min(max(1, i)+g[u][max(1, i)+1], f[u][i+1]);
for(int v:G[u]) if(v != fa)
f[u][i] = min(f[u][i], f[v][i+1]+g[u][i+1]-g[v][i]);
}
g[u][0] = f[u][0];
for(int i = 1; i <= n; i++) g[u][i] = min(g[u][i], g[u][i-1]);
}
int main() {
scanf("%d", &n);
for(int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
G[u].pb(v); G[v].pb(u);
}
dfs(1, 0);
printf("%dn", g[1][0]);
return 0;
}

最后

以上就是阳光吐司最近收集整理的关于【树形DP】Gym101667A Broadcast Stations的全部内容，更多相关【树形DP】Gym101667A内容请搜索靠谱客的其他文章。