首页 > 代码库 > HDU 1520 Anniversary party 树形DP
HDU 1520 Anniversary party 树形DP
题目大意:
员工参加周年晚会,如果没有遇到直接上司,那么员工会有一个开心值,我们要尽可能让员工的开心值最大
最开始输入n ,然后是1~n号员工对应的开心值
然后不断输入员工间的领导关系,L,K表示K是L的上司,直到输出0,0结束
这是第一次接触树形dp的题目,貌似也是最为推荐的题目,DP的思路是从别的大神地方得到的,
自己根据树形DP的思想写了一遍,对于树形DP的题目可以很容易看出,父节点总是只受到子节点的影响
所以我们总是由叶子到树根自底向上更新,通过dfs不断访问到叶子节点,最后再递归回来,直到到达root得到整体的最优解
这里有n个人,每个人都有来或者不来两种状态,那么我们定义一个
dp[N][2] 表示这两种状态
dp[i][0]表示 i 这个员工不来时所对应的 i 这棵子树得到的最优解
dp[i][1]表示 i 这个员工来时所对应的 i 这棵子树得到的最优解
dp[u][0] += max{dp[v][0] , dp[v][1]} v->u
dp[u][1] += max{dp[v][0]} v->u (v是u的子节点)
dp[u][1]要赋予初始值val[u] (u号对应的开心值)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 const int N = 6010; 7 int val[N] , dp[N][2] , flag[N] , first[N] , k; 8 9 struct Edge{10 int y , next;11 }e[N*N/2];12 13 void add_edge(int x , int y)14 {15 e[k].y = y , e[k].next = first[x];16 first[x] = k++;17 }18 19 void dfs(int u)20 {21 dp[u][1] = val[u];22 for(int i=first[u] ; i!=-1 ; i=e[i].next){23 int v = e[i].y;24 dfs(v);25 dp[u][0] += max(dp[v][0] , dp[v][1]);26 dp[u][1] += dp[v][0];27 }28 }29 30 int main()31 {32 // freopen("a.in" , "r" , stdin);33 int n , a , b;34 while(scanf("%d" , &n) == 1)35 {36 for(int i=1 ; i<=n ; i++)37 scanf("%d" , val+i);38 39 memset(flag , 0 , sizeof(flag)); //用来找树根40 memset(first , -1 , sizeof(first));41 while(scanf("%d%d" , &a , &b) , a&&b){42 add_edge(b , a);43 flag[a] = 1;44 }45 46 int root;47 /*48 不知道是不是只有一个根节点,还需考虑,49 但貌似直接过了,看来题目是保证只有一个50 最高级上司,也即唯一的根51 */52 for(int i = 1 ; i<=n ; i++)53 if(!flag[i]) root=i;54 55 memset(dp , 0 , sizeof(dp));56 dfs(root);57 /* for(int i = 1 ; i<=n ; i++){58 cout<<"i: "<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<endl;59 }*/60 printf("%d\n" , max(dp[root][0] , dp[root][1]));61 }62 return 0;63 }
HDU 1520 Anniversary party 树形DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。