GESP 题解库 / 7 级题解 / [GESP样题 七级] 最长不下降子序列 · 第 21 / 24 题
GESP样题 七级 · P10287 · 中等

最长不下降子序列

在有向无环图上,把每条路径的点权按顺序排成序列,求所有序列的 LNDS 长度的最大值。

🕸️
n, m ≤ 10⁵
节点数与边数
🔢
Aᵢ ≤ 10
点权值域很小
⚡
O((n + m) × 10)
时间复杂度
🎯
拓扑序 + 值域维度 DP
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨有一个包含 n 个节点、m 条边的有向无环图,节点编号为 1 … n,节点 i 的权值为 Aᵢ。对于图中的一条路径,按经过节点的先后顺序可以得到一个点权序列。小杨想知道:所有可能序列中最长不下降子序列长度的最大值是多少。

最长不下降子序列(LNDS)的定义是:原序列的一个子序列,它单调不降,并且是所有单调不降子序列中最长的那个。例如序列 [11, 12, 13, 9, 8, 17, 19] 的 LNDS 是 [11, 12, 13, 17, 19],长度为 5。

输入:第一行 n、m;第二行 A₁ … Aₙ;之后 m 行每行 uᵢ vᵢ,表示一条从 uᵢ 指向 vᵢ 的边。

💡
人话翻译:图里可能有很多条路径,每条路径都会"吐"出一个点权序列,我们要求的是所有序列里 LNDS 最长的那一个。
暴力枚举所有路径显然不行(路径数是指数级的)。
突破口有两个:① 路径前缀可以共享,所以按拓扑序做 DP;② Aᵢ ≤ 10 这个条件极小,小到可以把"值域"直接当成数组下标。
于是设两个状态:g[v] = "以 v 作为 LNDS 最后一个元素、路径终止于 v 时的最大长度";h[v][c] = "在路径终止于 v 的前提下,选出的元素都 ≤ c(c = 1 … 10)时能取到的最大长度"。
转移时:"以 v 结尾"就要接在某个前驱 u 的"末尾值 ≤ A_v"的最优前缀之后,所以 g[v] = 1 + max h[u][A_v]。

🔍 关键词提取

有向无环图拓扑排序值域维度 DP跳着选的子序列

已知条件

项目说明
输入第一行 n、m;第二行 A₁ … Aₙ;之后 m 行每行 uᵢ vᵢ
输出一个整数:所有路径序列中 LNDS 的最大长度
数据范围1 ≤ n ≤ 10⁵,1 ≤ m ≤ 10⁵,1 ≤ Aᵢ ≤ 10
图的性质有向无环图(DAG),可能有重边
子任务30%:n ≤ 10³ 且图是一条链;30%:Aᵢ ≤ 2;40%:Aᵢ ≤ 10
目标枚举所有路径 → 对每条路径求 LNDS → 取最大值

需要解决的问题

02
思维导图
整理解题思路的全貌
📐 g[v] 记"以 v 结尾",h[v][1…10] 记"前缀最优"
🧠 两个状态
g[v]:以 v 作为 LNDS 最后一个元素的最大长度
h[v][c]:路径终止于 v、选出的元素都 ≤ c 的最大长度
c 只需 1 … 10(因为 Aᵢ ≤ 10)
h 允许"一个都不选",即 0
🔁 转移
g[v] = 1 + max over 前驱 u of h[u][A_v]
没有前驱(或是全新的开头)则 g[v] = 1
h[v][c] = max(max over 前驱 u of h[u][c], c ≥ A_v ? g[v] : 0)
同一个点上:先算 g[v],再算 h[v][·]
🌐 拓扑序
按拓扑序处理,保证前驱都已算完
DAG 无环,所以一定能排出顺序
重边不影响正确性(只是重复遍历)
答案 = max over v of g[v]
⚠️ 易错点
只跟前驱的 Aᵤ 比较(漏掉"跳过中间点"的衔接)
忘记 g[v] 至少为 1(孤立点也要算 1)
值域数组开小(Aᵢ 到 10,下标要能取到 10)
先算 h[v] 再算 g[v](顺序反了会用到自己这一轮的信息)
03
样例手算推导
三个样例的完整推演

🧮 样例 1:n = 5, m = 4,答案 3

数据:A₁ … A₅ = 2, 10, 6, 3, 1;边为 5→2、2→3、3→1、1→4。这张图其实是一条链:5 → 2 → 3 → 1 → 4。

路径位置12345
节点52314
点权 A110623

点权序列是 [1, 10, 6, 2, 3],它的 LNDS 是 [1, 2, 3](取位置 1、4、5),长度为 3。

1
只比较"相邻点"会算出多少?

序列 [1, 10, 6, 2, 3] 里"相邻不下降"的连续段最长只有 2

(比如 2 → 3),

而真正的 LNDS [1, 2, 3] 中间隔着 10、6 两个点,

并不是"连着取的"。

所以必须用 h[v][c] 记住前缀最优

2
为什么 1 → 2 → 3 能接起来

位置 1 的值是 1,位置 4 的值是 2,位置 5 的值是 3

取子序列时只要求"在原序列中的下标递增",

不要求它们在路径上相邻,

所以 1、2、3 完全可以连成一条不下降序列。

✅ 长度 3

📊 DP 逐步推演(按拓扑序 5 → 2 → 3 → 1 → 4)

顺序节点 vA_v前驱 uh[u][A_v]g[v]说明
151无—1起点,只能自己成序列
22105h[5][10] = 12接在 5 后面:1, 10
3362h[2][6] = 1210 > 6,接不上,重新开始:1, 6
4123h[3][2] = 126 > 2,接不上,重新开始:1, 2
5431h[1][3] = 23关键一步:h[1][3] = 2 里存着 1, 2

max over v of g[v] = 3 ✓

🔑
第 5 行是本题的精华:处理节点 4(A₄ = 3)时,我们查 h[1][3]——它是"路径前缀里、末尾值 ≤ 3 的最优长度",结果是 2(来自 A₅ = 1 → A₁ = 2),于是 g[4] = 2 + 1 = 3。
如果只跟前驱的 A 值比较(A₁ = 2 ≤ A₄ = 3),就只能得到 2 —— 前面的那个 1 就丢了。

🧮 样例 2 与样例 3:多条路径里取最好的那条

这两个样例的图都有多条路径,必须比较不同路径上的结果。

1
样例 2:答案 4

数据:n = 6, m = 11,A = [1, 1, 2, 1, 1, 2]

取路径 5 → 1 → 2 → 6,点权序列是 [1, 1, 1, 2],

它本身就是不下降的,所以 LNDS 长度就是 4。

注意 A 的最大值只有 2,但"1 出现了很多次",

所以不下降序列照样能取到 4 个元素。

✅ 4

2
样例 3:答案 4

数据:n = 6, m = 11,A = [5, 9, 10, 5, 1, 6]

取路径 5 → 4 → 2 → 3,点权序列是 [1, 5, 9, 10],

它本身就是不下降的,LNDS 长度为 4。

若改走 5 → 4 → 3 → 1,序列是 [1, 5, 10, 5],

LNDS 只有 3([1, 5, 10] 或 [1, 5, 5]),更差。

✅ 4

样例最优路径路径上的点权序列取到的 LNDS长度
25 → 1 → 2 → 6[1, 1, 1, 2][1, 1, 1, 2]4
35 → 4 → 2 → 3[1, 5, 9, 10][1, 5, 9, 10]4
3(对照)5 → 4 → 3 → 1[1, 5, 10, 5][1, 5, 10]3
⚠️
样例 2 还说明了一件事:"点权的最大值"并不等于答案。样例 2 的 Aᵢ 只有 1 和 2,但因为"1"可以沿路径重复取到很多次,答案仍然能达到 4。
所以 DP 里的 h[v][c] 必须在"≤ c"这个条件下取最大,而不是只盯住"恰好等于 c"。
04
解法对比
拓扑序 + 值域 DP vs 枚举路径 / 只比相邻点

⚔️ 解法对比

🟢 拓扑序 + 值域维度 DP(推荐) 推荐

g[v] 记"以 v 结尾",h[v][1…10] 记"前缀里末尾值 ≤ c 的最优长度"

  • 时间 O((n + m) × 10) ≈ 2 × 10⁶
  • 空间 O(11n + m)
  • 代码约 35 行
  • 完美利用 Aᵢ ≤ 10 这一条件
💡
为什么必须带值域维度?因为"接在 v 前面"的那个元素不一定是 v 的直接前驱,所以需要把"前缀里末尾值 ≤ c 的最优解"整体存下来。值域只有 10,所以这个维度几乎不花钱。

🟠 枚举所有路径 / 只比相邻点

先把每条路径的点权序列求出来,再对每条序列求 LNDS

  • 路径数是指数级的,n = 10⁵ 时完全不可行
  • 只比"直接前驱的 Aᵤ ≤ A_v"会漏掉跳着衔接的情况
  • 链的子任务(30%)可以单独拿
  • 整体最多 30 分
⚠️
典型错误:很多人会写成 g[v] = 1 + max over 前驱 u 且 Aᵤ ≤ A_v of g[u],这在样例 1 上就会输出 2(正确答案是 3)。漏掉的正是"跳过中间点"的那条衔接。

📈 性能对比

方案复杂度可拿分数
拓扑序 + 值域 DPO((n + m) × 10)100 ✓
链的子任务单独求 LNDSO(n log n)30 ✓
枚举所有路径再求 LNDS路径数指数级❌ 0 分
05
算法流程图
按拓扑序做 g[v] 与 h[v][·]
开始读入 n、m、A[] 与 m 条有向边;建邻接表、前驱表与入度拓扑排序,得到节点的处理顺序 order按 order 依次取出节点 vg[v] = 1 + max over 前驱 u of h[u][A_v](无前驱则为 1)c 从 1 到 10:h[v][c] = max(前驱 h[c], g[v] 若 c ≥ A_v)所有节点都处理完了吗?输出 max over v of g[v]处理下一个节点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📐 LNDS 最大值计算器

第一行 n m;第二行 A 数组(每个 1 ~ 10);随后 m 行每行 u v(从 u 指向 v)。程序按拓扑序跑 DP 并展示每个点的 g 值。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(拓扑序 + 值域维度 DP)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);

    vector<vector<int>> adj(n + 1), pre(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        pre[v].push_back(u);
        indeg[v]++;
    }

    // 拓扑排序
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int w : adj[u])
            if (--indeg[w] == 0) q.push(w);
    }

    vector<int> g(n + 1, 0);                 // g[v]:以 v 结尾的 LNDS 长度
    vector<array<int, 11>> h(n + 1);         // h[v][c]:路径到 v 为止、元素都 ≤ c 的长度
    for (int i = 1; i <= n; i++) h[i].fill(0);

    int ans = 0;
    for (int v : order) {
        // 第一步:算"以 v 作为 LNDS 最后一个元素"的长度
        int best = 0;
        for (int u : pre[v]) best = max(best, h[u][A[v]]);
        g[v] = best + 1;                     // 至少为 1(v 单独成序列)

        // 第二步:把 v 的最新信息并进 h[v][1..10]
        for (int c = 1; c <= 10; c++) {
            int val = 0;
            for (int u : pre[v]) val = max(val, h[u][c]);   // 不用 v:继承前缀
            if (c >= A[v]) val = max(val, g[v]);            // 用 v 结尾
            h[v][c] = val;
        }

        ans = max(ans, g[v]);
    }

    printf("%d\n", ans);
    return 0;
}
🔑
为什么 h[v][c] 要对每个 c 都存一份?因为"v 后面要接的那个点的值"事先并不知道,可能是 1,也可能是 10。与其等查到再算,不如把"末尾值 ≤ c"的答案全部预算出来,到时候 O(1) 查询即可。
这就是"值域小"带来的红利:Aᵢ ≤ 10,所以只需 10 份答案。

📖 关键几行怎么看

代码作用为什么这样写
for (int u : pre[v]) best = max(best, h[u][A[v]]);核心查询找"末尾值 ≤ A_v"的最优前缀,把 v 接上去
g[v] = best + 1;以 v 结尾best 可能是 0(谁都接不上),此时 g[v] = 1
if (c >= A[v]) val = max(val, g[v]);v 自己也能当结尾只有当 c 不小于 A_v 时,v 才能作为"末尾值 ≤ c"的候选
h[v][c] = max(前缀继承, 用 v 结尾)信息合并两种来源:要么 v 不参与,要么 v 参与并且是最后一个
ans = max(ans, g[v])取答案任何 LNDS 都有"最后一个元素",所以扫描所有 g[v] 即可
⚠️
五个坑:① 写成"只跟前驱 Aᵤ 比较"(漏掉跳着衔接,样例 1 会输出 2);② 忘记 g[v] ≥ 1(孤立点、全部接不上的情况);③ h 的值域开小:Aᵢ 最大是 10,下标至少要能取到 10;④ 同一个点上先算 h[v] 再算 g[v](顺序反了相当于允许 v 接在自己后面);⑤ 拓扑排序后不检查 order.size() == n(题面保证是 DAG,但自查一下更稳)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 4
2 10 6 3 1
5 2 / 2 3 / 3 1 / 1 4
3题面样例 1(必须跳过中间的 10、6)
6 11
1 1 2 1 1 2
3 2 / 3 1 / 5 3 / 4 2 / 2 6 / 3 6 / 1 6 / 4 6 / 1 2 / 5 1 / 5 4
4题面样例 2(1 重复出现,答案能到 4)
6 11
5 9 10 5 1 6
5 4 / 5 2 / 4 2 / 3 1 / 5 3 / 6 1 / 4 1 / 4 3 / 5 1 / 2 3 / 2 1
4题面样例 3(走 5 → 4 → 2 → 3 最好)
2 1
5 5
1 2
2最小规模:两个相等的点首尾相接
3 2
3 2 1
1 2 / 2 3
1严格下降的链:只取得到 1 个元素
4 3
1 10 2 3
1 2 / 2 3 / 3 4
3必须"跳过"大值 10:取 1 → 2 → 3
4 3
2 2 2 2
1 2 / 1 3 / 3 4
3多条路径:走 1 → 3 → 4 全相等,得 3
✅
自查清单:① h 带了值域维度吗?② 按拓扑序处理了吗?③ 先算 g 后算 h 吗?④ 值域下标开到 10 了吗?

🚨 易错点清单

⚠️
只比相邻(直接前驱)的点权:LNDS 的上一个元素可能跳过若干中间点,必须用 h[v][c] 记住前缀最优。
⚠️
忘记 g[v] 至少为 1:若所有前驱都接不上(比如前驱的值都更大),g[v] 仍应是 1。
⚠️
值域数组开小:Aᵢ ∈ [1, 10],h 的下标必须取到 10。
⚠️
先算 h[v] 再算 g[v]:必须先用前驱的信息算出 g[v],再把 g[v] 并进 h[v][·]。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((n + m) × 10)
空间复杂度
O(11n + m)
n, m 最大
10⁵
运算量
约 2 × 10⁶

时间怎么算的?

空间都用在哪?

h 数组 (n + 1) × 11 个 int ≈ 4.4 MB,加上邻接表与前驱表 O(m),整体非常宽裕(内存限制 256 MB)。

✅ 约 200 万次操作,1 秒内轻松跑完。"Aᵢ ≤ 10"这个条件让值域维度只有 10,与题目给的另一个子任务(Aᵢ ≤ 2、30 分)恰好呼应——值域越小,这个做法越轻松。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// g[v]:以 v 作为 LNDS 最后一个元素、路径终止于 v 时的最大长度
// h[v][c]:路径终止于 v,选出的元素都 ≤ c 时的最大长度(c = 1 … 10)

// 按拓扑序处理 v
int best = 0;
for (int u : pre[v]) best = max(best, h[u][A[v]]);   // 接上"末尾 ≤ A_v"的最优前缀
g[v] = best + 1;                                      // 以 v 结尾

for (int c = 1; c <= 10; c++) {
    int val = 0;
    for (int u : pre[v]) val = max(val, h[u][c]);     // 不用 v:继承前驱路径
    if (c >= A[v]) val = max(val, g[v]);              // 用 v 结尾
    h[v][c] = val;
}
ans = max over v of g[v];

// 为什么值域维度必须单独记?
// 因为 LNDS 的"上一个元素"可以跳过若干个中间点,
// 不一定是路径上的直接前驱(样例 1 的 1 → 2 → 3 就是如此)。
// 有了 h[v][c],任意"要接的值"都能 O(1) 查到最优前缀。

// 若 A_i 的范围变大(比如 10^9),就要把值域维度换成
// 树状数组 / 线段树维护"末尾值 ≤ c 的最大长度",复杂度 O((n+m) log n)。

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
拓扑序 DP按拓扑序把前驱的信息汇总到当前点DAG 上的最长路、路径计数、依赖传递类问题
值域小维度Aᵢ ≤ 10,于是用 h[v][1…10] 记住"末尾 ≤ c"的最优解值域较小(几十以内)时把值域直接当数组下标
"跳着选"的衔接用前缀最优代替相邻比较LIS / LNDS、子序列类 DP 的通用套路
🌟
思考题:如果 Aᵢ 的范围放大到 10⁹(不再 ≤ 10),这个做法还成立吗?该怎么改?(提示:h 的值域维度开不下 10⁹ 个位置。可以按拓扑序做 DP,用树状数组 / 线段树维护"末尾值 ≤ c 的最大长度",复杂度变成 O((n + m) log n);也可以把所有出现过 Aᵢ 离散化后再维护前缀最大值。可见"Aᵢ ≤ 10"这个条件,正是本做法能把值域当数组下标的根本原因。)