首页 > 代码库 > hdu1520树形dp入门

hdu1520树形dp入门

2024-09-03 14:47:05   218人阅读

题目链接

题意：要开派对，邀请了上司就不能邀请他的下属，邀请了下属就不能邀请他的上司，每个人有一个值，求邀请的人的总值最大

第一行给出一个数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入门


联系
我们