首页 > 代码库 > zoj2315New Year Bonus Grant Dp

zoj2315New Year Bonus Grant Dp

树dp吧,就是它取了 就不能取它儿子,它儿子最多有一个可以取。

然后对于每种dp[x][1] 表示 x 取了, dp[x][1] = ∑ dp[son[x][0] +1,但是如果他是1  ,他自己不能取自己,这里要注意下。

dp[x][0]= max((∑dp[son[x]][0])-dp[son[x]][0] + dp[son[x]][1];

#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 555555;int len ;int head[maxn];int dp[maxn][2];int son[maxn];struct Node{    int next;int to;}e[maxn];void add(int from,int to){    e[len].to = to;    e[len].next =head[from];    head[from] = len++;}void gao(int x){    dp[x][0] = dp[x][1] = 0;son[x] = -1;    int sum = 0;    for(int i = head[x];i!=-1;i=e[i].next){        int cc=e[i].to;        gao(cc);        sum+=dp[cc][0];    }    if(x!=1)    dp[x][1] = sum+1;    else dp[x][1] = sum;    for(int i =  head[x];i!=-1;i=e[i].next){        int cc=e[i].to;        int t  = sum - dp[cc][0]+dp[cc][1];        if(t>dp[x][0]){            dp[x][0] = t; son[x] = cc;        }    }    if(sum>dp[x][0]) son[x] = -1,dp[x][0] = sum;}int ans[maxn];int cnt;void showpath(int x,int flag){    if(flag == 1) ans[cnt++] = x;    if(flag==0){        for(int i = head[x];i!=-1;i=e[i].next){            int cc=e[i].to;            if(cc==son[x]) showpath(cc,1);            else            showpath(cc,0);        }    }    else{        for(int i= head[x];i!=-1;i=e[i].next){            int cc=e[i].to;            showpath(cc,0);        }    }}int main(){    int T,n,a;    cin>>T;    int Icase=0;    while(T--){        if(Icase++) printf("\n");        cin>>n;        cnt = 0;        len = 0 ;        memset(head,-1,sizeof(head));        for(int i =2;i<=n;i++){            scanf("%d",&a);            add(a,i);        }        gao(1);        showpath(1,0);        printf("%d\n",1000*max(dp[1][0],dp[1][1]));        sort(ans,ans+cnt);        printf("%d",ans[0]);        for(int i=1;i<cnt;i++)            printf(" %d",ans[i]);        cout<<endl;    }    return 0;}

 

zoj2315New Year Bonus Grant Dp