马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
P10287 [GESP样题 七级] 最长不降落子序列 题解
Link：Luogu - P10287
[size=4
]标题形貌
小杨有个包罗 n n n 个节点 m m m 条边的有向无环图，此中节点的编号为 1 1 1 到 n n n。
对于编号为 i i i 的节点，其权值为 w i w_i wi。对于图中的一条路径，根据路径上的颠末节点的先后序次可以得到一个节点权值的序列，小杨想知道图中全部大概序列中最长不降落子序列的最大长度。
注：给定一个序列 S S S，其最长不降落子序列 S ′ S
9; S′ 是原序列中的如下子序列：整个子序列 S ′ S
9; S′ 单调不降，而且是序列中最长的单调不降子序列。比方，给定序列 S = [ 11 , 12 , 13
, 9 , 8 , 17 , 19 ] S = [11,12,13
,9,8,17,19] S=[11,12,13
,9,8,17,19]，其最长不降落子序列为 S ′ = [ 11 , 12 , 13
, 17 , 19 ] S
9;=[11,12,13
,17,19] S′=[11,12,13
,17,19]，长度为 5 5 5。
[size=4
]输入格式
第一行包罗两个正整数 n , m n,m n,m，体现节点数和边数。
第二行包罗 n n n个正整数 A 1 , A 2 , … A n A_1, A_2, \dots A_n A1,A2,…An，体现节点 1 1 1 到 n n n 的点权。
之后 m m m 行每行包罗两个正整数 u i , v i u_i, v_i ui,vi，体现第 i i i 条边毗连节点 u i u_i ui 和 v i v_i vi，方向为从 u i u_i ui 到 v i v_i vi。
[size=4
]输特别式
输出一行一个整数体现答案。
[size=4
]样例 #1
[size=3
]样例输入 #1
- 5 4
- 2 10 6 3
- 1
- 5 2
- 2 3
- 3
- 1
- 1 4
]样例输出 #1
[size=4
]样例 #2
[size=3
]样例输入 #2
- 6 111 1 2 1 1 23
- 23
- 15 3
- 4
- 22 63
- 61 64
- 61 25 15 4
]样例输出 #2
[size=4
]样例 #3
[size=3
]样例输入 #3
- 6 115 9 10 5 1 65 4
- 5 24
- 23
- 15 3
- 6 14
- 14
- 3
- 5 12 3
- 2 1
]样例输出 #3
[size=4
]提示
[size=3
]数据规模与约定
子任务分值 n ≤ n\le n≤ A i ≤ A_i \le Ai≤特殊约定 1 1 1 3
0 3
0 3
0 1 0 3
10^3
103
10 10 10输入的图是一条链 2 2 2 3
0 3
0 3
0 1 0 5 10^5 105 2 2 2无 3
3
3
4
0 4
0 4
0 1 0 5 10^5 105 10 10 10无对全部的测试数据，包管 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105， 1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^5 1≤m≤105， 1 ≤ A i ≤ 10 1 \leq A_i \leq 10 1≤Ai≤10。
[size=4
]解题思绪
提示：这是一道对初学者来说比力有难度的图上 dp，不明白的话可以在草稿纸上模仿一下，如许会更易懂一些。
看到标题，肯定是图论
3
;dp的题。看到“路径上的颠末节点的先后序次”这句话，就知道要用拓扑排序。
然后，根据拓扑序，对每条边举办法态规划。但直接设 f [ i ] f f 体现以 i i i 末了的 LIS 长度，每碰到一条边就更新一次。如许时间复杂度是 O ( n m ) O(nm) O(nm) 的，会超时。
然后观察标题标“缺点”： 1 ≤ A [ i ] ≤ 10 1 \le A \le 10 1≤A≤10，这么小？于是，第二种 LIS 思绪来了：设 f [ i ] [ j ] f[j] f[j] 体现从某处到点 i i i，末了数为 j j j 的LIS长度。
然后转移来了（重点）：对于 v v v 的某个前驱节点 u u u：
- 将点 v v v 加到点 u u u 的 LIS 反面。 f [ v ] [ A [ i ] ] = m a x { f [ u ] [ i ] 
3
; 1 , f [ v ] [ A [ i ] ] } f[v][A]=max\{f
3
;1, f[v][A]\} f[v][A]=max{f
3
;1,f[v][A]}，此中 1 ≤ i ≤ A [ u ] 1 \le i \le A 1≤i≤A
- 用 u u u 更换点 v v v，也大概得到更优的答案。 f [ v ] [ i ] = m a x { f [ u ] [ i ] , f [ v ] [ i ] } f[v]=max\{f, f[v]\} f[v]=max{f,f[v]}，此中 1 ≤ i ≤ 10 1 \le i \le10 1≤i≤10。
末了答案：全部 f [ i ] [ j ] f[j] f[j] 的最大值。包管 1 ≤ i ≤ n , 1 ≤ j ≤ 10 1 \le i \le n, 1 \le j \le 10 1≤i≤n,1≤j≤10。
[size=4
]AC Code
- #include <bits/stdc
- 3
- ;
- 3
- ;.h>using namespace std;typedef long long ll;const int maxn = 1e5 
- 3
- ; 7;int n, m, A[maxn], ind[maxn]; // ind[i]体现节点i的入度int f[maxn][15];vector <int> G[maxn]; // 存图void solve(){ cin >> n >> m; for(int i = 1; i <= n; i 
- 3
- ;
- 3
- ;) cin >> A[i]; for(int u, v, i = 1; i <= m; i 
- 3
- ;
- 3
- ;){ cin >> u >> v; G[u].push_back(v); 
- 3
- ;
- 3
- ; ind[v]; // 入度
- 3
- ;1 } queue <int> Q; // 拓扑排序的队列 for(int i = 1; i <= n; i 
- 3
- ;
- 3
- ;){ if(ind[i] == 0) Q.push(i); f[i][A[i]] = 1; // 初始化：到点i以A[i]末了的LIS长度为1（就是点i自己） } while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int v : G[u]){ -- ind[v]; if(ind[v] == 0){ Q.push(v); // 入度变为0，入队 } // dp转移 for(int i = 1; i <= A[v]; i 
- 3
- ;
- 3
- ;){ f[v][A[v]] = max(f[u][i] 
- 3
- ; 1, f[v][A[v]]); } for(int i = 1; i <= 10; i 
- 3
- ;
- 3
- ;){ f[v][i] = max(f[u][i], f[v][i]); } } } // 责备部答案的最大值 int maxn = -1e9; for(int i = 1; i <= n; i 
- 3
- ;
- 3
- ;){ for(int j = 1; j <= 10; j 
- 3
- ;
- 3
- ;) maxn = max(maxn, f[i][j]); } cout << maxn << 
- 9;\n
- 9;;}signed main(){ ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); solve(); return 0;}
]End
感谢各人的观看！祝各人 AC！
这里是 YLCHUP，拜拜ヾ(•ω•`)o
倾销个人洛谷博客、洛谷主页。
.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金 |
发表于 2026-4-24 08:52:55