gym 101667 A -Broadcast Stations【树形dp】

A 树形dp

题目大意：

一棵5e3的树，可以选择一些点，放上基站，如果u上的基站价值为d，那么距离u小于等于d的点都会被覆盖，问使得整棵树被覆盖需要的最小价值。

题目分析

设 $f[u][i]$ 表示从 u这个点 ，向外最多能覆盖 到距离为i的点，且他的子树都被覆盖的最小价值。

那么我们考虑 $f[u][i]$ 可能是在u这个点建立了一个价值为i的基站，也可能是他的子树能够覆盖到 i+1

因此 我们还需要统计 u这个点 距离他的i的子树全被覆盖所需的最小价值

定义为 g[u][i]
$g[u][i]=\sum g[v][i-1]$

所以我们考虑 $f[u][i]=min(f[v][i+1]-g[v][i],j)+g[u][i+1]$

$f[v][i+1]-g[v][i]$ 表示这个v这个点最多能往外延伸到i+1的距离，（也就是删去的v的子树）
这样在树上进行dp就可以了。

考虑边界情况
我们在计算 f[u][0] 的时候， 不能直接选择 j ，因为只有 u这一个点的时候也需要消耗 1的价值，所以我们特判 f[u][0]的情况

代码详情

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3+50;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
vector<int>G[maxn];
int g[maxn][maxn];
int f[maxn][maxn];
int n;
void dfs(int u,int fa)
{
//	cout<<u<<" fa= "<<fa<<endl;
for(int i=0;i<G[u].size();i++)
{
int v = G[u][i];
if(v!=fa)
{
dfs(v,u);
for(int j=1;j<=n;j++)
{
g[u][j] += g[v][j-1];
}
}
}
f[u][n]= n; //表示 U点 覆盖所有点需要的价值，最大是n 
g[u][0] =n; // 初始化g[u][0]
u的子树全覆盖的情况
for(int i=n-1;i>=0;i--)
{
if(i!=0)
f[u][i] = min(i+g[u][i+1],f[u][i+1]); //在某个位置新建一个基站 
else if(i==0)
//特判=0的时候， f[u][0]表示子树都被覆盖，只覆盖u这个点的时候也需要1个 
{
f[u][i] = min(1+g[u][2],f[u][i+1]);
}
for(int j=0;j<G[u].size();j++)
{
int v = G[u][j];
if(v!=fa)
{
f[u][i] = min(f[u][i],f[v][i+1]-g[v][i]+g[u][i+1]);
}
}
}
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);
memset(g,0,sizeof(g));
memset(f,0,sizeof(f));
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
//	cout<<1<<endl;
dfs(1,0);
//	cout<<2<<endl;
printf("%dn",g[1][0]);
return 0;
}

最后

以上就是文艺草丛为你收集整理的gym 101667 A -Broadcast Stations【树形dp】的全部内容，希望文章能够帮你解决gym 101667 A -Broadcast Stations【树形dp】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。