树状DP第一题,,,刚开始的时候看了一个描述,说是要把多叉树改成二叉树,结果就以为每道题都要这样,倒腾了很久都没开始。。。然后后来看了一下代码。。。。
其实这道题算是入门题,不难,但是有一点不大清楚,就是如果有分离开的两棵树要怎么办。可能是我题目没有看清楚。。。。
跑了110ms...
#include <stdio.h> #include <string.h> #define maxn 6010 int father[maxn],n; int dp[maxn][2]; int vis[maxn]; int max(int x,int y) { if(x>y) return x; else return y; } void find(int x) { int i,j,k; vis[x]=1; for(i=1;i<=n;i++) if(!vis[i]&&father[i]==x) { find(i); dp[x][0]+=max(dp[i][0],dp[i][1]); // printf("**%d %d %d %d\n",dp[i][0],dp[i][1],dp[x][0],i); dp[x][1]+=dp[i][0]; } } int main() { while(scanf("%d",&n)!=EOF) { int i,j,k; int root=0; memset(dp,0,sizeof(dp)); memset(father,0,sizeof(father)); memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) scanf("%d",&dp[i][1]); // printf("$$%d\n",dp[7]) while(scanf("%d%d",&j,&k)!=EOF&&j+k) { father[j]=k; root=k; } find(k); printf("%d\n",max(dp[root][1],dp[root][0])); } return 0; }