HIGH93 没有上司的舞会

题目描述

公司准备举办一场晚会，共有 名员工。每名员工都有一个“气氛值”，邀请他们可以为晚会增加对应的气氛值。

规则是：如果邀请了一名员工，那么他的直接上司就不能被邀请。

已知公司的层级关系是一棵树，根节点是老板。请求出一个邀请方案，使得晚会的总气氛值最大。

解题思路

这是一个经典的树形动态规划问题，通常被称为“没有上司的舞会”。核心约束是：一个节点和它的父节点不能同时被选择。

1. 模型抽象

  • 图结构: 公司的组织架构是一棵树。我们需要先根据输入的上下级关系建树，并找到树的根节点（没有上司的员工）。
  • 决策: 对于每个员工（树中的节点），我们都有两种决策：邀请他，或不邀请他。这个决策会影响到他的下属是否能被邀请。

2. 状态定义

为了捕捉这两种决策及其后续影响，我们为每个节点定义一个包含两个状态的DP数组：

  • : 表示在以员工 为根的子树（即 和他的所有下属）中，不邀请员工 时，能获得的最大气氛值。
  • : 表示在以员工 为根的的子树中，邀请员工 时，能获得的最大气氛值。

我们的目标是，在计算完根节点 root 的DP值后，取 和 中的较大者。

3. 状态转移

我们通过一次深度优先搜索 (DFS)，以自底向上（后序遍历）的方式来计算DP值。对于当前员工节点 ，我们先递归地计算完他所有直接下属 的DP值，然后用这些结果来更新 的DP值。

  • 计算 (不邀请 ):

    • 如果我们不邀请员工 ，那么对于他的每一个直接下属 ，我们既可以邀请 ，也可以不邀请 。为了使气氛值最大化，我们应该为每个下属 选择最优的方案，即 。
    • 因此， 的值等于他所有直接下属 的最优气氛值之和。
    • 状态转移方程:

  • 计算 (邀请 ):

    • 如果我们邀请员工 ，那么我们首先能获得他自己的气氛值 。
    • 根据规则，他的所有直接下属 都不能被邀请。因此，我们只能从每个下属 的子树中获取在“不邀请 ”这种情况下的最大气氛值，即 。
    • 状态转移方程:

4. 寻找根节点

输入的上下级关系并未直接给出根节点。我们可以用一个布尔数组 has_parent 来记录每个员工是否是别人的下属。遍历完所有关系后，那个 has_parent 仍为 false 的员工就是公司的老板，即树的根节点。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> w;
vector<vector<int>> adj;
vector<vector<long long>> dp;

void dfs(int u, int p) {
    // 状态初始化
    dp[u][1] = w[u-1]; // 邀请u，获得其气氛值
    dp[u][0] = 0;      // 不邀请u，初始气氛值为0

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        
        // 累加来自子树的贡献
        dp[u][0] += max(dp[v][0], dp[v][1]); // u不来，v可来可不来
        dp[u][1] += dp[v][0];                // u来了，v一定不能来
    }
}

int main() {
    int n;
    cin >> n;

    w.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
    }
    
    // n=1 是特殊情况，没有边
    if (n == 1) {
        cout << w[0] << endl;
        return 0;
    }

    adj.resize(n + 1);
    vector<bool> has_parent(n + 1, false);
    for (int i = 0; i < n - 1; ++i) {
        int boss, subordinate;
        cin >> boss >> subordinate;
        adj[boss].push_back(subordinate);
        adj[subordinate].push_back(boss);
        has_parent[subordinate] = true;
    }

    int root = -1;
    for (int i = 1; i <= n; ++i) {
        if (!has_parent[i]) {
            root = i;
            break;
        }
    }

    dp.assign(n + 1, vector<long long>(2, 0));
    dfs(root, -1);

    cout << max(dp[root][0], dp[root][1]) << endl;

    return 0;
}

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main {
    static int[] w;
    static List<Integer>[] adj;
    static long[][] dp;

    private static void dfs(int u, int p) {
        // 状态初始化
        dp[u][1] = w[u - 1]; // 邀请u，获得其气氛值
        dp[u][0] = 0;       // 不邀请u，初始气氛值为0

        for (int v : adj[u]) {
            if (v == p) continue;
            dfs(v, u);

            // 累加来自子树的贡献
            dp[u][0] += Math.max(dp[v][0], dp[v][1]); // u不来，v可来可不来
            dp[u][1] += dp[v][0];                     // u来了，v一定不能来
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
        }
        
        if (n == 1) {
            System.out.println(w[0]);
            return;
        }

        adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        boolean[] hasParent = new boolean[n + 1];

        for (int i = 0; i < n - 1; i++) {
            int boss = sc.nextInt(); 
            int subordinate = sc.nextInt();
            adj[boss].add(subordinate);
            adj[subordinate].add(boss);
            hasParent[subordinate] = true;
        }

        int root = -1;
        for (int i = 1; i <= n; i++) {
            if (!hasParent[i]) {
                root = i;
                break;
            }
        }

        dp = new long[n + 1][2];
        dfs(root, -1);

        System.out.println(Math.max(dp[root][0], dp[root][1]));
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(2005) 

def dfs(u, p, w, adj, dp):
    # 状态初始化
    dp[u][1] = w[u - 1] # 邀请u
    dp[u][0] = 0      # 不邀请u

    for v in adj[u]:
        if v == p:
            continue
        dfs(v, u, w, adj, dp)
        
        dp[u][0] += max(dp[v][0], dp[v][1])
        dp[u][1] += dp[v][0]

def main():
    try:
        n_str = input()
        if not n_str: return
        n = int(n_str)
        w = list(map(int, input().split()))
    
        if n == 1:
            print(w[0])
            return

        adj = [[] for _ in range(n + 1)]
        has_parent = [False] * (n + 1)
    
        for _ in range(n-1):
            boss, subordinate = map(int, input().split())
            adj[boss].append(subordinate)
            adj[subordinate].append(boss)
            has_parent[subordinate] = True

        root = -1
        for i in range(1, n + 1):
            if not has_parent[i]:
                root = i
                break
            
        dp = [[0, 0] for _ in range(n + 1)]
        dfs(root, -1, w, adj, dp)
    
        print(max(dp[root][0], dp[root][1]))
    except (IOError, ValueError):
        # 某些平台空输入会报错，进行保护
        return

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 树形DP
  • 时间复杂度: 。建树和寻找根节点需要 。DFS 遍历会访问每个节点和每条边一次，所以也是 。
  • 空间复杂度: 。需要 的空间来存储员工的气氛值、邻接表（树结构）、has_parent 数组以及DP表。