[洛谷 1352,poj 2342]没有上司的舞会

题目链接

https://www.luogu.org/problemnew/show/P1352

题解

我们定义状态\(f[i][0/1]\)代表以\(i\)为根的子树的最优解(第二维的值为0代表\(i\)不参加舞会的情况,1代表\(i\)参加舞会的情况)

显然,我们可以得到下面两个状态转移方程(其中\(x\)为\(i\)的子节点):

  • \(f(i,0) = \sum\max {f(x,1),f(x,0)}\)(上司不参加舞会时,下属可以参加,也可以不参加)
  • \(f(i,1) = \sum{f(x,0)} + a_i\)(上司参加舞会时,下属都不会参加)

我们可以通过 DFS,在返回上一层时更新当前节点的最优解。

#include <cstdio>
#include <algorithm>
using namespace std;
struct edge
{
 int v,next;
}e[6005];
int head[6005],n,cnt,f[6005][2],ans,is_h[6005],vis[6005];
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void calc(int k)
{
 vis[k]=1;
 for(int i=head[k];i;i=e[i].next)
 {
  if(vis[e[i].v])continue;
  calc(e[i].v);
  f[k][1]+=f[e[i].v][0];
  f[k][0]+=max(f[e[i].v][0],f[e[i].v][1]);
 }
 return;
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&f[i][1]);
 for(int i=1;i<n;i++)
 {
  int l,k;
  scanf("%d%d",&l,&k);
  is_h[l]=1;
  addedge(k,l);
 }
 for(int i=1;i<=n;i++)
  if(!is_h[i])
  {
   calc(i);
   printf("%d",max(f[i][1],f[i][0]));
   return 0;
  }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注