首页 > 代码库 > POJ2342-Anniversary party-树形DP入门
POJ2342-Anniversary party-树形DP入门
链接：poj.org/problem?id=2342
大意：一棵上下级关系树，直接上司不能和下属一起出席，每人都有权值，求出席party的人价值和最大值。
树形DP：dp[i]// 以i号人为根的关系树，dp [i][1]表示当前树 i 号人出席的价值和最大值，表示当前树 i 号人不出席的价值和最大值。
方程：dp[i][0] +=Σ max(dp[son][0],dp[son][1]);
dp[i][1] +=Σ dp[son][0];
dp[son] 在dp[i]之前算，所以DFS。
#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>using namespace std;long long dp[6666][2];int cnt;int head[6666];int v[6666];int in[6666];struct edge{ int to,next;}E[6666];void addedge(int from , int to){ E[cnt].to = to; E[cnt].next = head[from]; head[from] = cnt++;}void dfs(int now){ for (int i = head[now] ; i != -1 ; i = E[i].next ) { int to = E[i].to; dfs(to); dp[now][0] += max(dp[to][1],dp[to][0]); dp[now][1] += dp[to][0]; } return;}int main(){ int N; //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); cin >> N; memset(dp,0,sizeof(dp)); for (int i = 1; i <= N ; i++) { cin >> dp[i][1]; } int a,b; cnt = 0; memset(head,-1,sizeof head); long long start = N*(N+1)/2; while (cin >> a >> b &&a!=0&&b!=0) { addedge(b,a); start -= (long long)a; } dfs((int)start); cout << max(dp[start][1],dp[start][0]) << endl;}
POJ2342-Anniversary party-树形DP入门
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。