当前位置:   article > 正文

洛谷 P2016 战略游戏 题解_洛谷算法大赛方格游戏

洛谷算法大赛方格游戏

题目:P2016 战略游戏

DP - 树形DP

题目大意

给出一棵树,如果在一个点 x x x 放了一个士兵,该士兵将会覆盖所有与点 x x x 直接相邻的边。求最少放多少个士兵,使得所有边都被覆盖

解题思路

很简单的一道题,跟P2899 [USACO08JAN]手机网络Cell Phone Network非常相似,只不过改成了覆盖边

对于每个点,我们考虑放不放士兵,所以要开一维去储存是否放士兵的状态

f [ x ] [ 0 ] f[x][0] f[x][0] 表示以 x x x 为根的子树中,点 x x x 不放士兵所需要的最小士兵数量
f [ x ] [ 1 ] f[x][1] f[x][1] 则表示以 x x x 为根的子树中,点 x x x 放士兵所需要的最小士兵数量

转移方程:
f [ x ] [ 0 ] = ∑ f [ y ] [ 1 ] f[x][0]=\sum f[y][1] f[x][0]=f[y][1],其中 y y y x x x 的子节点
f [ x ] [ 1 ] = 1 + ∑ m i n ( f [ y ] [ 0 ] , f [ y ] [ 1 ] ) f[x][1]=1+ \sum min(f[y][0],f[y][1]) f[x][1]=1+min(f[y][0],f[y][1]),因为 x x x y y y 的边已经被覆盖了,所以点 y y y 放不放都没关系

最后答案就是 m i n ( f [ 1 ] [ 0 ] , f [ 1 ] [ 1 ] ) min(f[1][0],f[1][1]) min(f[1][0],f[1][1])
PS: 这里点 1 1 1 作为根,其实拿任意一个点做根都可以

代码

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
const int Maxn=1520,inf=0x3f3f3f3f;
vector <int> e[Maxn];
int f[Maxn][2];
int n;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
void dfs(int x,int fa)
{
	f[x][1]=1;
	for(int i=0;i<e[x].size();++i)
	{
		int y=e[x][i];
		if(y==fa)continue;
		dfs(y,x);
		f[x][1]+=min(f[y][1],f[y][0]);
		f[x][0]+=f[y][1];
	}
}
int main()
{
//	freopen("in.txt","r",stdin);
	n=read();
	for(int i=1;i<=n;++i)
	{
		int x=read()+1,cnt=read(); // 程序中储存的节点编号是 1~n
		while(cnt--)
		{
			int y=read()+1;
			e[x].push_back(y);
			e[y].push_back(x);
		}
	}
	dfs(1,0);
	printf("%d\n",min(f[1][1],f[1][0]));
	return 0;
}
  • 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
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/996538
推荐阅读
相关标签
  

闽ICP备14008679号