hdu1054 Strategic Game(树形DP)

时间:2023-02-03 07:33:31

嘿嘿,我的第一道树形DP

题意:用最少的点覆盖整棵树,看一下Sample Input 就知道题意。

分析:

在树上做一个动态规划

【状态】:

dp[i][0] 为以 i 为根节点,并且该节点不放,所需要的最少的点数

dp[i][1] 为以 i 为根节点,并且该节点放,所需要的最少的点数

 

【转移方程】:

dp[i][0]=sum(dp[son[i][j]][1]) 该点不放的话,那么它的儿子节点必须都放,这样之间的边才可以被覆盖

dp[i][1]=sum(min(dp[son[i][j]][0],dp[son[i][j]][1])) 该点放的话,那么它的儿子节点就有两种决策,一种是放,一种是不放,取 min 就行了

#include<iostream>
using namespace std;
int dp[1505][2],f[1505],ans,n;
int son[1505][1505],size[1505];
int dfs(int pos,int val)
{
	if(dp[pos][val]!=INT_MIN)
		return dp[pos][val];
	int sum=val;
	for(int i=0;i<size[pos];i++)
	{
		if(val==1)
			sum+=min(dfs(son[pos][i],0),dfs(son[pos][i],1));
		else sum+=dfs(son[pos][i],1);//当前节点不选,则子节点必须要选
	}
	return dp[pos][val]=sum;
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		for(int i=0;i<n;i++)
		{
			f[i]=i;
			dp[i][1]=dp[i][0]=INT_MIN;
		}
		for(int i=0;i<n;i++)
		{
			int x,m;
			scanf("%d:(%d)",&x,&m);
			size[x]=m;
			for(int j=0;j<size[x];j++)
			{
				scanf("%d",&son[x][j]);
				f[son[x][j]]=x;
			}
		}
		for(int i=0;i<n;i++)
		{
			if(f[i]==i)
			{
				ans=min(dfs(i,0),dfs(i,1));
				break;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}