C++ luogu1352没有上司的舞会 from_树形DP

luogu1352没有上司的舞会

分析(树形DP模板题):

没学树形DP的,看一下。

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

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

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

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

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

所以

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

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

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

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

 STL之vector

原文地址:https://www.cnblogs.com/mzyczly/p/10828739.html