题解 P1352 【没有上司的舞会】

· · 题解

这道题作为一道十分经典的树形dp，它显然是像我们这样的新手拿来学习和试手的一道好题。

首先我们们分析一下这道题，对于每一个人，它所做的决定对上司和下属都有影响，我们可以只看一方，也就是上司对下属的影响，因为这样的影响是相互的。

状态如果为f[i]表示第i个人的位置能获得最大的幸福行吗？

由于我们的选择具有后效性，因为你去或不去对下属有影响，那显然不行。遇到这种情况我们该怎么办？

加一维

由于后效性实质上是我们对于状态的性质不够清楚，所以我们再加一维以实现就算你加还是不加我们都可以记录下来。所以状态其实是很好想的。想出状态后，容易推出方程为

dp[i][0]=sum(max(dp[son][1],dp[son][0]));

显然，你不去，那下属就可以想去就去。

dp[i][1]=sum(dp[son][0])+happy[i];

显然你去了那下属就一定不能去。

由此我们就可以愉快的DFS了。

但是

如果我们的人数相当多且是一条链的时候就容易造成爆栈，那这我们有如何解决呢?方法有三

  1. 开一个数组手动实现栈。

  2. bfs后用for循环

  3. 拓扑排序

第一个想必大家都会写，而且其与dfs相似，所以不再赘述。

那为啥会讲后两种呢？

因为有时候dfs并不好写，所以我们会把它转化为bfs+for或者拓扑，大家可以看一下，dfs和这两种写法的推导有的是不一样的。特别是和这题的拓扑写法，可以仔细看一下。

那么首先说下bfs

我们很容易发现树形dp它为什么一般会是dfs形式？因为树形dp的状态大多是一颗颗子树，它传递状态过程一般都是先求出最下层再往上更新。所以对于每一个点，我们在求解它的值的过程中，需要求出它每一个子节点的解。那有什么方法我们可以用数组和for循环实现这样的求解呢？没错，就是bfs过程中的队列。由于队列中的点都是先入的父亲节点后入的子节点，所以我们求解的时候只要把循环顺序反过来就可以了。以下代码

#include<bits/stdc++.h>
using namespace std;
int t=0,que[6005],happy[6005],fa[6005];
vector<int>son[6007];
queue<int> q;
bool vis[6005];
int dp[6005][2];
void bfs(int s)
{
    q.push(s);
    vis[s]=1;
    que[++t]=s;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        int x=son[u].size();
        for(int i=0;i<x;i++)
        {
            if(!vis[son[u][i]])
            {
                vis[son[u][i]]=1;
                q.push(son[u][i]);
                que[++t]=son[u][i];
            }
        }
    }
    return ;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        scanf("%d",&happy[i]);
    }
        int a,b;
    while(scanf("%d %d",&a,&b))
    {
        if(a==0&&b==0)
        break;
        fa[a]=b;
        son[b].push_back(a);
    }
    int s=n;
    while(s!=fa[s])
    s=fa[s];
    bfs(s);
    for(int i=t;i>0;i--)
    {
        int u=que[i];
        int x=son[u].size();
        for(int j=0;j<x;j++)
        {
            int v=son[u][j];
            dp[u][0]+=max(dp[v][0],dp[v][1]);
            dp[u][1]=max(dp[u][1],dp[u][1]+dp[v][0]);
        }
        dp[u][1]+=happy[u];
    }
    printf("%d",max(dp[s][0],dp[s][1]));
    return 0;
}

接下来我们谈谈拓扑排序做法。

先来回顾一下，拓扑排序的时候我们其实是从根到子节点，那么如何实现从子节点返回根节点的求解过程呢？反向连边存入度。没错，反向，就可以轻易实现这样的求解。可以自己手动模拟一下。然后对于这样的求解，我们可以在边求拓扑排序边更新答案。

至于为啥其实很好想的，可以自己推推（其实我懒了）

#include<bits/stdc++.h>
using namespace std;
int happy[6005];
int ru[6005];
int fa[6005];
int dp[6005][2]; 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&happy[i]); 
    } 
    int a,b;
    while(scanf("%d %d",&a,&b))
    {
        if(a == 0&&b == 0)
        break;
        ru[b]++;
        fa[a] = b;
    } 
    queue<int>q;
    for(int i = 1;i <= n;i++)
    {
        if(ru[i] == 0)
        q.push(i);
    }
    int maxn = 0; 
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        dp[u][1] += happy[u];
        maxn = max(dp[u][1],maxn);
        maxn = max(dp[u][0],maxn);
        ru[fa[u]] --;
        if(ru[fa[u]] == 0)
        q.push(fa[u]); 
        dp[fa[u]][0] = max(dp[fa[u]][0] + dp[u][0],dp[fa[u]][0] + dp[u][1]);
        dp[fa[u]][1] += dp[u][0] >= 0 ? dp[u][0] : 0;

    }
    printf("%d",maxn);
}

希望这篇题解能对大家有点帮助

还有这是我的博客来看看也好，就是luogu的。

希望顶顶，我也会写一些其他树形dp的题解，谢谢大家啦

博客