NekoNowcoder

Appearance

上班 - 题解 ​

标签与难度 ​

标签: 树形DP, 背包问题, 动态规划, 图论, 深度优先搜索, 树上背包 难度: 2200

题目大意喵~ ​

你好呀，未来的算法大师！我是你们的我向导，今天我们要解决一个关于小 D 上班的有趣问题，喵~

小 D 的城市是一个 N×MN \times M 的网格。她的家在左上角 (0, 0)，公司在右下角 (n, m)。她每天都要走路去上班，每秒可以移动到相邻的格子上。

这个城市里有些路是不通的，被设置了障碍。一个重要的提示是，这些障碍使得整个城市地图（把格子看作点，能走的路看作边）变成了一棵树！也就是说，从任何一个格子到另一个格子，只有一条不走回头路的简单路径，是不是很神奇呐？

每个格子 (i, j) 都有一个美丽值 v[i][j]。小 D 希望在规定的时间 T 秒内到达公司，并且途中经过的所有不同格子的美丽值之和最大。如果一个格子路过好几次，它的美丽值也只算一次哦。

我们的任务就是帮小 D 规划一条完美的上班路线，让她在不迟到的前提下，欣赏到最多的美景，喵~

解题思路分析 ​

这道题看起来像一个寻路问题，但加上了时间和价值的限制，就变得复杂起来了呢。不过别怕，跟着我一步步来，问题就会变得像毛线球一样顺从啦！

核心洞察：树形结构 + 额外时间 ​

首先，最关键的一点是题目保证了整个网格图是一棵树。在树上，任意两点之间的简单路径是唯一的。所以，从家 (0, 0) 到公司 (n, m) 的最短路径也是唯一的。我们就把这条唯一的路径叫做“主路”吧！

走完主路需要的时间是固定的，等于主路上的边数（也就是 主路格子数 - 1）。设这个最短时间是 min_time。

小 D 总共有 T 秒时间。那么多出来的时间 extra_time = T - min_time 能用来做什么呢？当然是去主路旁边的小巷子（子树）里探险啦！

（一个简单的示意图，红色是主路，蓝色是绕路探险）

每次探险，比如从主路上的点 p 跑到旁边分支上的点 v，逛一圈再回来，这个过程是“有去有回”的。从 p 到 v 花 1 秒，从 v 回到 p 又要花 1 秒。所以，每探索一个不在主路上的新格子，至少要花费 2 秒的额外时间（去1秒，回1秒）。

这意味着，我们拥有的 extra_time 实际上可以转化为 extra_time / 2 次“一去一回”的探索机会。我们就把这个机会叫做“探索步数”好了。我们的目标就是用这些探索步数，去访问那些不在主路上的、美丽值最高的格子组合！

树上背包，我来啦！ ​

这个问题完美地转化成了一个经典的组合优化问题——背包问题！

  1. 物品: 主路旁边伸出去的每一个“小树枝”（子树）都可以看作一组物品。
  2. 背包容量: 我们的背包容量就是总的“探索步数”，即 k = (T - min_time) / 2。
  3. 物品的重量和价值: 对于一个子树，如果我们决定进去探索 j 个格子，那么就需要花费 j 个探索步数（因为访问 j 个新格子需要 2*j 秒的来回时间）。这 j 个格子的美丽值总和，就是我们获得的“价值”。

所以，问题分解为两个阶段：

阶段一：计算每个子树的探索价值（树上背包DP）

对于树上的任意一个节点 u，我们需要知道在以它为根的子树里，选择访问 j 个节点能获得的最大美丽值总和是多少。

我们定义一个 DP 状态： dp[u][j]dp[u][j]：在以节点 u 为根的子树中，选择一个包含 u 的、大小为 j 的连通块，能够获得的最大美丽值总和。

这个DP可以通过一次从叶节点到根节点（后序遍历）的深度优先搜索来完成。

  • 基本情况: 对于一个节点 u，最少也要访问它自己，所以 dp[u][1] = beauty[u]。
  • 状态转移: 当我们计算 dp[u] 时，我们已经计算好了它所有孩子 v 的 dp[v]。我们可以像做背包问题一样，把每个孩子的 DP 结果合并到父节点 u 上。

    dpnew[u][i+j]=max⁡(dpnew[u][i+j],dpcurrent[u][i]+dp[v][j])dp_{new}[u][i+j] = \max(dp_{new}[u][i+j], dp_{current}[u][i] + dp[v][j])

    这里 i 是在 u 和它已经合并过的子树中选择的节点数，j 是在当前孩子 v 的子树中选择的节点数。

通过这个过程，我们对树上所有节点 u 都计算出了 dp[u][j]。

阶段二：组合所有“分支”的价值（最终背包问题）

现在，我们已经知道了每个小分支的“性价比”，接下来就要做最终的选择了！

  1. 首先，用一次DFS找到从家到公司的主路，并把主路上的所有格子标记出来。
  2. 计算主路上所有格子的基础美丽值 base_beauty 和最短时间 min_time。
  3. 计算我们的“背包容量”，也就是总探索步数 budget = (T - min_time) / 2。
  4. 创建一个最终的背包数组 final_dp[k]，表示花费 k 个探索步数能获得的最大额外美丽值。
  5. 遍历主路上的每一个节点 p。对于 p 的每一个不属于主路的邻居 v，v 就代表一个可以去探险的“小树枝”的入口。
  6. 这个小树枝（以v为根的子树）就是一个物品组。我们可以花 j 步去探索它，获得 dp[v][j] 的价值。我们把这个物品组放入我们的最终背包。
cpp
// 对于每个在主路p旁边的分支v
for (int k = budget; k >= 0; --k) {       // 背包容量
    for (int j = 1; j <= sz[v]; ++j) {   // 物品（在v子树中访问j个点）
        if (k >= j) { // 如果背包能装下
            final_dp[k] = max(final_dp[k], final_dp[k - j] + dp[v][j]);
        }
    }
}
  1. 所有分支都处理完后，final_dp[budget] 就是我们能获得的最大额外美丽值。

最终答案就是 base_beauty + final_dp[budget]，喵~

代码实现 ​

这是我根据上面的思路，精心重构的一份代码！变量名和注释都力求清晰，希望能帮助你理解哦~

cpp
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const long long INF = 1e18; // 用一个足够大的数表示无穷大

int N, M, T;
int total_nodes;

// 使用邻接表来存储树的结构
vector<int> adj[10201];
int beauty[10201];

// 树形DP相关数组
int parent[10201];
int subtree_size[10201];
vector<long long> dp[10201]; // dp[u][j]: 在u的子树中访问j个点的最大美丽值

// 标记主路上的节点
bool is_on_main_path[10201];

// 将二维坐标 (r, c) 转换为一维节点ID
int get_id(int r, int c) {
    return r * (M + 1) + c;
}

// 阶段一: 树上背包DP，通过DFS计算每个子树的价值
void tree_knapsack_dfs(int u, int p) {
    parent[u] = p;
    subtree_size[u] = 1;

    // 初始化dp[u]: 至少访问自己，大小为1，价值为beauty[u]
    dp[u].assign(2, -INF);
    dp[u][0] = 0; // 访问0个节点价值为0 (理论上不会用到, 但为背包合并提供方便)
    dp[u][1] = beauty[u];

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

        tree_knapsack_dfs(v, u);

        // 创建临时dp表用于合并
        vector<long long> temp_dp(subtree_size[u] + subtree_size[v] + 1, -INF);

        // 背包合并：将v子树的dp信息合并到u
        for (int i = 0; i <= subtree_size[u]; ++i) {
            if (dp[u][i] == -INF) continue;
            for (int j = 0; j <= subtree_size[v]; ++j) {
                if (dp[v][j] == -INF) continue;
                temp_dp[i + j] = max(temp_dp[i + j], dp[u][i] + dp[v][j]);
            }
        }
        
        // 更新u的dp表和子树大小
        dp[u] = temp_dp;
        subtree_size[u] += subtree_size[v];
    }
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> T;
    total_nodes = (N + 1) * (M + 1);

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            cin >> beauty[get_id(i, j)];
        }
    }

    // 用一个二维布尔数组记录障碍
    vector<vector<bool>> banned(total_nodes, vector<bool>(total_nodes, false));
    for (int i = 0; i < N * (M + 1) + M * (N + 1) - total_nodes + 1; ++i) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        int u = get_id(r1, c1);
        int v = get_id(r2, c2);
        banned[u][v] = banned[v][u] = true;
    }

    // 根据障碍情况建图
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            int u = get_id(i, j);
            // 向下
            if (i < N) {
                int v = get_id(i + 1, j);
                if (!banned[u][v]) {
                    adj[u].push_back(v);
                    adj[v].push_back(u);
                }
            }
            // 向右
            if (j < M) {
                int v = get_id(i, j + 1);
                if (!banned[u][v]) {
                    adj[u].push_back(v);
                    adj[v].push_back(u);
                }
            }
        }
    }

    // 阶段一: 从(0,0)开始DFS，完成整个树的背包预处理
    int start_node = get_id(0, 0);
    tree_knapsack_dfs(start_node, -1);

    // 阶段二: 寻找主路，并进行最终的背包组合
    long long base_beauty = 0;
    vector<int> main_path;
    int end_node = get_id(N, M);

    // 通过parent指针回溯找到主路
    for (int curr = end_node; curr != -1; curr = parent[curr]) {
        main_path.push_back(curr);
        is_on_main_path[curr] = true;
    }
    
    // 计算主路的基础信息
    for(int node : main_path) {
        base_beauty += beauty[node];
    }
    int min_time = main_path.size() - 1;

    if (T < min_time) {
        // 时间不够，根本到不了公司QAQ
        // (根据题意这种情况可能不会发生)
        // 实际上这种情况答案就是-1或者某个特定值, 但题目似乎保证有解。
        // 如果只走主路，价值是base_beauty，但是超时了。
        // 题目问的是T秒内能到达的路径，所以这种情况应该是无解。
        // 为了安全起见，我们认为这种情况不会发生。
    }

    int detour_budget = (T - min_time) / 2;
    if (detour_budget < 0) detour_budget = 0;

    // 最终背包DP: final_dp[k] 表示用k步探索能获得的最大额外美丽值
    vector<long long> final_dp(detour_budget + 1, 0);

    // 遍历主路上的点，把旁边的分支作为物品组加入背包
    for (int p_node : main_path) {
        for (int v_node : adj[p_node]) {
            // 如果邻居v不是主路上的点 (也不是p的父节点)
            if (!is_on_main_path[v_node]) {
                // v_node就是分支的根
                // 合并v_node子树的背包信息
                for (int k = detour_budget; k >= 1; --k) {
                    for (int j = 1; j <= subtree_size[v_node] && j <= k; ++j) {
                         if(dp[v_node][j] > -INF) // 确保这个状态是可达的
                            final_dp[k] = max(final_dp[k], final_dp[k - j] + dp[v_node][j]);
                    }
                }
            }
        }
    }
    
    cout << base_beauty + final_dp[detour_budget] << endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(V2)O(V^2)，其中 VV 是网格中的总节点数，即 V=(N+1)×(M+1)V = (N+1) \times (M+1)。

    • 建图: O(NM)O(NM)。
    • 树上背包DP: tree_knapsack_dfs 是复杂度的主要来源。在每个节点 u，我们会将它的子节点 v 的DP表合并上来，这个操作的复杂度是 O(size(ucurrent)×size(v))O(\text{size}(u_{current}) \times \text{size}(v))。对于整棵树，所有这些合并操作的总复杂度是 O(V2)O(V^2)。
    • 最终背包: 遍历主路上的每个节点，将其旁边的分支（物品组）加入背包。总的来说，所有分支的节点数之和小于 VV，每个物品的成本最大为 detour_budget。这一步的复杂度大约是 O(V×detour_budget)O(V \times \text{detour\_budget})。
    • 总体来看，树上背包的 O(V2)O(V^2) 是瓶颈。对于 N,M≤100N, M \le 100, V≈10000V \approx 10000, V2≈108V^2 \approx 10^8，计算量在可接受范围内。

  • 空间复杂度: O(V2)O(V^2)。

    • 空间复杂度的瓶颈同样在于存储树上背包的DP表 dp。在最坏的情况下（例如一条链），DP表的总大小会达到 O(V2)O(V^2)。vector<long long> dp[10201] 的总大小会是这个级别。

知识点总结 ​

这真是一道非常经典的复合型题目，融合了多种算法思想，做完之后一定收获满满，喵~

  1. 问题转化: 能够从复杂的题目描述中，识别出其核心是“树上唯一路径”+“额外时间利用”的模型，这是解题的第一步，也是最重要的一步。
  2. 树形DP: 这是解决树上最优化问题的强大武器。本题中，我们用它来预处理出每个子树的“价值”，体现了“分而治之”的思想。
  3. 背包问题: 无论是树上背包的合并过程，还是最终选择分支的组合过程，都运用了背包问题的核心思想。特别是“分组背包”模型，每个分支就是一组物品，我们需要从每组中至多选一个（比如，在分支v里探索j个点）。
  4. 图的遍历(DFS): 无论是建立父子关系、计算子树大小，还是后序遍历执行DP，都离不开DFS这个基本功。

掌握了树上背包，很多类似的树形问题都会变得容易起来！希望这篇题解能帮到你，继续加油，你就是最棒的，喵~！