首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。