HDOJ 题目1520 Anniversary party(树形dp)
Anniversary party
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6271 Accepted Submission(s): 2820
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
5
#include<stdio.h> #include<string.h> #define max(a,b) (a>b?a:b) struct s { int u,v,next; }edge[3000100]; int a[6060],dp[6060][2],dig[6060],head[6060],vis[6060],cnt; void add(int u,int v) { edge[cnt].u=u; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u) { vis[u]=1; dp[u][1]=a[u]; int i; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!vis[v]) { dfs(v); dp[u][0]+=max(dp[v][0],dp[v][1]); dp[u][1]+=dp[v][0]; } } } int main() { int n; while(scanf("%d",&n)!=EOF) { int i; for(i=1;i<=n;i++) { scanf("%d",&a[i]); } int u,v; cnt=0; memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); memset(dig,0,sizeof(dig)); memset(vis,0,sizeof(vis)); while(scanf("%d%d",&v,&u),u||v) { add(u,v); dig[v]++; } int s; for(i=1;i<=n;i++) { if(!dig[i]) { s=i; } } dfs(s); printf("%d\n",max(dp[s][0],dp[s][1])); } }
相关文章
- Java实现 LeetCode 826 安排工作以达到最大收益(暴力DP)
- Java实现 蓝桥杯 算法提高 天天向上(DP)
- ZOJ 3725 Painting Storages(DP+排列组合)
- 01背包问题(DP 复习)
- POJ题目1947 Rebuilding Roads(树形dp)
- Codeforces 437E The Child and Polygon(间隔DP)
- HDU-4628 Pieces 如压力DP
- POJ 3934 Queue(DP)
- HDU4960Another OCD Patient(间隙dp,后座DP)
- HDU 3681 BFS&像缩进DP&二分法
- 有意思的DP(CF360B Levko and Array)
- DFS——单词分割,原来还是要使用cached dp才能避免不超时