首页 > 代码库 > hdu1520树形dp入门
hdu1520树形dp入门
题目链接
题意:要开派对,邀请了上司就不能邀请他的下属,邀请了下属就不能邀请他的上司,每个人有一个值,求邀请的人的总值最大
第一行给出一个数n,代表有n个人。
下面n行分别给出n个人的的值
再下面n行每行给出L,K;K是L的上司
以0 0结束一组输入
树形dp:把每个人看成一个点,则该点有两个状态:邀请或没被邀请
定义f[u][0]为节点没被邀请时的值;f[u][1]为节点被邀请时的值
状态转移方程:
f[u][0]=sum(max(f[v][0],f[v][1])//v为u的下属
f[u][1]=sum(f[v][0])//上司邀请了,则下属只有没被邀请这种状态
要求总值,则显然要求max(f[U][0],f[U][1])//U为根节点
用dfs遍历树用
f[u][0]=0;
f[u][1]=value[u];
vis[u]=1;
在递归中初始化每个节点的状态
达到实现动态规划的目的
代码实现:
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<vector>
6 #include<algorithm>
7 using namespace std;
8 vector<int>vec[6005];//储存节点的子节点
9 int value[6005];
10 int vis[6005];
11 int f[6005][2];
12 int in[6005];//入度找根节点:根节点入度为0
13 void dfs(int u)
14 {
15 f[u][0]=0;
16 f[u][1]=value[u];
17 vis[u]=1;
18 for(int i=0;i<vec[u].size();i++)
19 {
20 int v=vec[u][i];
21 if(vis[v])continue;
22 dfs(v);
23 f[u][0]+=max(f[v][0],f[v][1]);
24 f[u][1]+=f[v][0];
25 }
26 return;
27 }
28 int main()
29 {
30 int n,u,v,i,j,k;
31 while(~scanf("%d",&n)&&n)
32 {
33 for(i=0;i<=n;i++)vec[i].clear();
34 for(i=1;i<=n;i++)scanf("%d",&value[i]);
35 memset(in,0,sizeof(in));
36 while(~scanf("%d%d",&v,&u)&&(u+v))
37 {
38 vec[u].push_back(v);
39 in[v]++;
40 }
41 for(i=1;i<=n;i++)
42 {
43 if(!in[i])
44 {
45 memset(vis,0,sizeof(vis));
46 memset(f,0,sizeof(f));
47 dfs(i);
48 printf("%d\n",max(f[i][0],f[i][1]));
49 break;
50 }
51 }
52 }
53 return 0;
54 }
hdu1520树形dp入门
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。