Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贪心树形DP

Posted by Swal_MJ at 2010-12-11 13:49:33 on Problem 1463 and last updated at 2010-12-11 13:57:46
  其实好像用不到状态转移方程,不必枚举这个点是否放士兵,取最值。因为,这是一颗有根树,从出度为0的根结点开始往下找,
1.找到某个点的儿子是叶子的话,那这个点一定要放士兵的(贪心,给儿子放的话只能照顾到一条边,给老子的话至少有1条边);
2.某个点的所有(是所有,不是1个!)儿子都放士兵的话,那父亲就不用放了(照顾到了),否则父亲就一定的放。
  这样搜完,根节点即为所求最小士兵数,有点记忆搜索的问道。
副代码:344ms
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
vector<int>t[1513];
bool used[1515];
int f[1513]; 
int dp(int root)
{
	int i,j,son;
	int sum=0;
	for(i=0;i<t[root].size();i++)
	{
		son=t[root][i];
		if(t[son].size()==0)
			used[root]=true;
		else  sum+=dp(son);
		
	}
	bool kk=true;
	for(i=0;i<t[root].size();i++)
	  kk=kk&&used[t[root][i]];
		if(kk&&!used[root])
		{
			f[root]=sum;
			used[root]=false;
		}
		else
		{
			f[root]=sum+1;
			used[root]=true;
		}
	return f[root];
}

int main()
{
	int i,j,a,b,n,tmp;
	bool visit[1513]={0};
	while(scanf("%d",&n)!=EOF)
	{
		for(j=1;j<=n;j++)
		{
			  scanf("%d:(%d)",&a,&b);
			for(i=0;i<b;i++)
			{
				scanf("%d",&tmp);
				visit[tmp]=1;
				t[a].push_back(tmp);
			}
	   }
		for(i=0;i<n;i++)
			if(!visit[i])
				break;
		   dp(i);
		   cout<<f[i]<<endl;
		for(i=0;i<n;i++)
			t[i].clear();
		memset(visit,0,sizeof(visit));
		memset(used,0,sizeof(used));
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator