在有向无环图上,把每条路径的点权按顺序排成序列,求所有序列的 LNDS 长度的最大值。
小杨有一个包含 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ᵢ 的边。
g[v] = "以 v 作为 LNDS 最后一个元素、路径终止于 v 时的最大长度";h[v][c] = "在路径终止于 v 的前提下,选出的元素都 ≤ c(c = 1 … 10)时能取到的最大长度"。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 → 取最大值 |
[1, 10, 6, 2, 3],LNDS 是 [1, 2, 3]:它取了 A₅ = 1、A₁ = 2、A₄ = 3,其中 1 和 2 之间隔着 10、6 两个点。所以"只比较相邻两点的值"一定会漏掉这种跳着衔接的情况h[v][c] 这个"值域维度"的数组:它把"路径前缀上、末尾值 ≤ c 的最优长度"都存下来了,这样无论要接的值是多大,都能 O(1) 查到最优前缀h 是一个 10¹⁰ 级别都装不下的东西变成了11 × (n + 1) 的小数组。值域小 = 可以拿值当下标,这是本做法的命门g[v] 与 h[v][·] 只依赖前驱的信息,拓扑序保证处理 v 时它的所有前驱都已算完数据:A₁ … A₅ = 2, 10, 6, 3, 1;边为 5→2、2→3、3→1、1→4。这张图其实是一条链:5 → 2 → 3 → 1 → 4。
| 路径位置 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 节点 | 5 | 2 | 3 | 1 | 4 |
| 点权 A | 1 | 10 | 6 | 2 | 3 |
点权序列是 [1, 10, 6, 2, 3],它的 LNDS 是 [1, 2, 3](取位置 1、4、5),长度为 3。
序列 [1, 10, 6, 2, 3] 里"相邻不下降"的连续段最长只有 2
(比如 2 → 3),
而真正的 LNDS [1, 2, 3] 中间隔着 10、6 两个点,
并不是"连着取的"。
所以必须用 h[v][c] 记住前缀最优
位置 1 的值是 1,位置 4 的值是 2,位置 5 的值是 3
取子序列时只要求"在原序列中的下标递增",
不要求它们在路径上相邻,
所以 1、2、3 完全可以连成一条不下降序列。
✅ 长度 3
| 顺序 | 节点 v | A_v | 前驱 u | h[u][A_v] | g[v] | 说明 |
|---|---|---|---|---|---|---|
| 1 | 5 | 1 | 无 | — | 1 | 起点,只能自己成序列 |
| 2 | 2 | 10 | 5 | h[5][10] = 1 | 2 | 接在 5 后面:1, 10 |
| 3 | 3 | 6 | 2 | h[2][6] = 1 | 2 | 10 > 6,接不上,重新开始:1, 6 |
| 4 | 1 | 2 | 3 | h[3][2] = 1 | 2 | 6 > 2,接不上,重新开始:1, 2 |
| 5 | 4 | 3 | 1 | h[1][3] = 2 | 3 | 关键一步:h[1][3] = 2 里存着 1, 2 |
max over v of g[v] = 3 ✓
h[1][3]——它是"路径前缀里、末尾值 ≤ 3 的最优长度",结果是 2(来自 A₅ = 1 → A₁ = 2),于是 g[4] = 2 + 1 = 3。这两个样例的图都有多条路径,必须比较不同路径上的结果。
数据: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
数据: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 | 长度 |
|---|---|---|---|---|
| 2 | 5 → 1 → 2 → 6 | [1, 1, 1, 2] | [1, 1, 1, 2] | 4 |
| 3 | 5 → 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 |
g[v] 记"以 v 结尾",h[v][1…10] 记"前缀里末尾值 ≤ c 的最优长度"
先把每条路径的点权序列求出来,再对每条序列求 LNDS
g[v] = 1 + max over 前驱 u 且 Aᵤ ≤ A_v of g[u],这在样例 1 上就会输出 2(正确答案是 3)。漏掉的正是"跳过中间点"的那条衔接。| 方案 | 复杂度 | 可拿分数 |
|---|---|---|
| 拓扑序 + 值域 DP | O((n + m) × 10) | 100 ✓ |
| 链的子任务单独求 LNDS | O(n log n) | 30 ✓ |
| 枚举所有路径再求 LNDS | 路径数指数级 | ❌ 0 分 |
第一行 n m;第二行 A 数组(每个 1 ~ 10);随后 m 行每行 u v(从 u 指向 v)。程序按拓扑序跑 DP 并展示每个点的 g 值。
点按钮开始 →
#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) 查询即可。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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] 即可 |
g[v] ≥ 1(孤立点、全部接不上的情况);③ h 的值域开小:Aᵢ 最大是 10,下标至少要能取到 10;④ 同一个点上先算 h[v] 再算 g[v](顺序反了相当于允许 v 接在自己后面);⑤ 拓扑排序后不检查 order.size() == n(题面保证是 DAG,但自查一下更稳)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 4 | 3 | 题面样例 1(必须跳过中间的 10、6) |
6 11 | 4 | 题面样例 2(1 重复出现,答案能到 4) |
6 11 | 4 | 题面样例 3(走 5 → 4 → 2 → 3 最好) |
2 1 | 2 | 最小规模:两个相等的点首尾相接 |
3 2 | 1 | 严格下降的链:只取得到 1 个元素 |
4 3 | 3 | 必须"跳过"大值 10:取 1 → 2 → 3 |
4 3 | 3 | 多条路径:走 1 → 3 → 4 全相等,得 3 |
h 带了值域维度吗?② 按拓扑序处理了吗?③ 先算 g 后算 h 吗?④ 值域下标开到 10 了吗?h[v][c] 记住前缀最优。g[v] 仍应是 1。h 的下标必须取到 10。g[v],再把 g[v] 并进 h[v][·]。h[u][A_v] 需要遍历前驱(合计 O(m))h[v][1 … 10],每个 c 都要遍历前驱 → 合计 10 × O(m)h 数组 (n + 1) × 11 个 int ≈ 4.4 MB,加上邻接表与前驱表 O(m),整体非常宽裕(内存限制 256 MB)。
✅ 约 200 万次操作,1 秒内轻松跑完。"Aᵢ ≤ 10"这个条件让值域维度只有 10,与题目给的另一个子任务(Aᵢ ≤ 2、30 分)恰好呼应——值域越小,这个做法越轻松。
// 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 的通用套路 |
h 的值域维度开不下 10⁹ 个位置。可以按拓扑序做 DP,用树状数组 / 线段树维护"末尾值 ≤ c 的最大长度",复杂度变成 O((n + m) log n);也可以把所有出现过 Aᵢ 离散化后再维护前缀最大值。可见"Aᵢ ≤ 10"这个条件,正是本做法能把值域当数组下标的根本原因。)