這題很簡單，而且題面描述也很清楚，我就不放樣例了。 設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);新聞熱點
疑難解答
