luogu1352没有上司的舞会

分析(树形DP模板题):

没学树形DP的,看一下。

把该题抽象到一颗树中,设i的下属就是他的儿子,则有两种情况:

如果i参加,他的儿子就不能参加。

如果i不参加,他的儿子可参加可不参加。

所以设f[i][1]表示i参加,f[i][0]表示i不参加,则有

f[i][]+=max(f[j][],f[j][]);
f[i][]+=f[j][]+w[i]; //j是i的儿子

所以

ans=max(f[i][],f[i][])   //最大快乐指数

得到基础代码:(很粗略,不过好懂)

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=;
int f[maxn][],n,r[maxn];
int son[maxn][maxn],tot[maxn];
int vis[maxn];
int end;
void tree_dp(int x)
{
for (int i=;i<=tot[x];i++)
{
int y=son[x][i]; //哪个儿子
tree_dp(y); //刷新y的快乐指数
f[x][]+=max(f[y][],f[y][]);
f[x][]+=f[y][];
}
}
void work()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",&f[i][]); //父亲(上司)要去的情况,要加本身的快乐指数
int k,l;
for (int i=;i<=n;i++)
{
scanf("%d%d",&l,&k);
if(l!=&&k!=)
{
son[k][++tot[k]]=l;
vis[l]=; //l是儿子
}
}
for (int i=;i<=n;i++)
{
if(!vis[i]) //找根节点(非儿子)
{
end=i;
break;
}
}
tree_dp(end);
printf("%d",max(f[end][],f[end][]));
}
int main()
{
work();
return ;
}

在这里就要说一下vector了,真的很好用

STL之vector

05-23 07:07