战略游戏

题目背景

Bob 喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。

题目描述

他要建立一个古城堡,城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。

注意,某个士兵在一个结点上时,与该结点相连的所有边将都可以被了望到。

请你编一程序,给定一树,帮 Bob 计算出他需要放置最少的士兵。

输入格式

第一行一个整数 (n),表示树中结点的数目。

第二行至第 (n+1) 行,每行描述每个结点信息,依次为:一个整数 (i),代表该结点标号,一个自然数 (k),代表后面有 (k) 条无向边与结点 (i) 相连。接下来 (k) 个整数,分别是每条边的另一个结点标号 (r_1),(r_2),(cdots,r_k) ,表示 (i) 与这些点间各有一条无向边相连。

对于一个(n) 个结点的树,结点标号在 (0)(n-1) 之间,在输入数据中每条边只出现一次。保证输入是一棵树。

输入输出样例

输入
4
0 1 1
1 2 2 3
2 0
3 0
输出
1

说明/提示
数据规模与约定

对于全部的测试点,保证 (1≤n≤1500)

sol

一道(tree dp),题目大意:给你(n)个点,每个点有(k)条无向边连接,一颗无根树,现在要在点上放士兵,所放的士兵可以保护这个点所连的边,问你最少需要多少条边,才能让士兵把所有点保护起来
题目意思清晰的一道题,是(tree dp)中的存在性问题,与没有上司的舞会非常相似。因为是一颗无根树,所以根放在哪里都是一样的。

我们分类讨论一下:

  • 1假如(u)这个节点没有放,是不是就可以从他的子节点((v))的放了这种情况转移过来。
  • 2假如(u)这个节点放了,就可以从他的子节点的放了与没有放取最小值转移过来。

我们定义dp[u][1]表示这个节点放了,dp[u][0]表示这个节点没有放,因为是统计个数所以要加上
DP状态转移方程如下:

[ egin{cases} dp[u][0]=sum dp[v][1];\ dp[u][1]=sum min(dp[v][0],dp[v][1]); end{cases} ]

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=3100;
int n;
int now[maxn],son[maxn],pre[maxn],tot;
void add(int x,int y){//前向星存图 
	pre[++tot]=now[x];
	son[tot]=y;
	now[x]=tot;
}
int dp[maxn][2];
void dfs(int u,int fa){
	dp[u][1]=1,dp[u][0]=0;//附上初值 
	for(int i=now[u];i;i=pre[i]){
		int v=son[i];
		if(v==fa)continue;
		dfs(v,u);
		dp[u][0]+=dp[v][1];
		dp[u][1]+=min(dp[v][1],dp[v][0]);//做treedp 
	}
}
int main(){
	memset(dp,0x3f,sizeof(dp));//因为是取最小值,所以要数组初始化最大 
	cin>>n;
	for(int i=1,x,y;i<=n;i++){
		cin>>x>>y;++x;//为了避免0节点报错,先加上1 
		for(int j=1,z;j<=y;j++)cin>>z,++z,add(x,z),add(z,x);
	}
	dfs(1,0);//因为是无根树,我们就默认从1开始跑 
	cout<<min(dp[1][0],dp[1][1])<<endl;//分类讨论取最小值 
	return 0;
}
原文地址:https://www.cnblogs.com/qzwer/p/13396895.html