这题很简单，而且题面描述也很清楚，我就不放样例了。 设f[i][2]表示第i个点选（1）或不选（0），以i为根的这棵子树能选的最大价值。易得转移方程为： f[i][0]=∑(max(f[s][0],f[s][1])) f[i][1]=∑(f[s][0])+w[i] ————————————————by zlx 显然啦要用dfs去更新； 就是在dp前先dfs算出其儿子的值； 最简单的树形dp吧；
#include<iostream>#include<cstdio>using namespace std;struct cs{ int to,next;}a[3000];int head[3001],w[3001],f[3001][2];bool b[3001];int n,m,x,y,z,ll,ans,sum,S,E;void init(int x,int y){ ll++; a[ll].to=y; a[ll].next=head[x]; head[x]=ll;}void dfs(int now){ for(int k=head[now];k;k=a[k].next){ dfs(a[k].to); f[now][0]+=max(f[a[k].to][1],f[a[k].to][0]); f[now][1]+=f[a[k].to][0]; } f[now][1]+=w[now];}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&w[i]); while(scanf("%d%d",&x,&y)!=EOF){ if(!x&&!y)break; init(y,x); b[x]=1; } for(int i=1;i<=n;i++)if(!b[i])S=i; dfs(S); PRintf("%d",max(f[S][1],f[S][0]));}新闻热点
疑难解答
