首页 > 代码库 > [洛谷P1352][codevs1380]没有上司的舞会
[洛谷P1352][codevs1380]没有上司的舞会
题目大意：某大学有N个职员，编号为1~N。他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但如果某个职员的上司来参加舞会了，那么这个职员就不肯参加舞会了。求最大的快乐指数。
解题思路：经典的树形dp。我们设f[i][0]表示i参加时能获得的最大快乐指数，f[i][1]表示i不参加时能获得的最大快乐指数。
那么如果i参加，则他的下属一定不能参加，就在他参加获得的快乐指数上加上他所有下属不参加时的最大快乐指数(f[p][1],p是i的某个下属)
如果i不参加，他的下属可以参加也可以不参加，那么对于每个下属，我们把他参加和不参加时的快乐指数的较大值（$max(f[p][1],f[p][0])$）加到f[i][1]中即可。
最后的答案为$max(f[root][1],f[root][0])$，root表示“校长”。
时间复杂度最坏也就$O(n)$，即整棵树成为一条链的情况。
C++ Code：
#include<cstdio>#include"cctype"#include<vector>using namespace std;#define C c=getchar()int boss[6050],a[6050],n,f[6050][2];//f[i][0]表示i参加时能获得的最大快乐指数，f[i][1]表示i不参加时能获得的最大快乐指数。vector<int> e[6050];inline int readint(){ char C; bool b=false; while(!isdigit(c))b=c==‘-‘,C; int p=0; while(isdigit(c)) p=(p<<3)+(p<<1)+c-‘0‘,C; if(b)p=-p; return p;}void dp(int t){ f[t][0]=a[t]; f[t][1]=0; for(int i=0;i<e[t].size();++i){ int to=e[t][i]; dp(to); f[t][0]+=f[to][1]; f[t][1]+=(f[to][0]<f[to][1])?(f[to][1]):(f[to][0]); }}int main(){ n=readint(); int x,y; for(int i=1;i<=n;++i)a[i]=readint(); while((x=readint())&&(y=readint())){ boss[x]=y; e[y].push_back(x); } for(int i=1;i<=n;++i) if(!boss[i]){//寻找“校长”。 dp(i); printf("%d\n",(f[i][0]<f[i][1])?f[i][1]:f[i][0]); return 0; }}
[洛谷P1352][codevs1380]没有上司的舞会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。