当前位置：首页 > news >正文

【C++】P10287 [GESP样题七级] 最长不下降子序列题解_动态规划dp_图论_拓扑排序_洛谷_算法竞赛

news 来源：原创 2024/9/20 5:54:45

P10287 [GESP样题七级] 最长不下降子序列题解

Link：Luogu - P10287

文章目录

P10287 [GESP样题七级] 最长不下降子序列题解
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- - 样例输入 #1
  - 样例输出 #1
- 样例 #2
- - 样例输入 #2
  - 样例输出 #2
- 样例 #3
- - 样例输入 #3
  - 样例输出 #3
- 提示
- - 数据规模与约定
- 解题思路
- AC Code
- End

题目描述

小杨有个包含 $n$ 个节点 $m$ 条边的有向无环图，其中节点的编号为 $1$ 到 $n$ 。

对于编号为 $i$ 的节点，其权值为 $w_i$ 。对于图中的一条路径，根据路径上的经过节点的先后顺序可以得到一个节点权值的序列，小杨想知道图中所有可能序列中最长不下降子序列的最大长度。

注：给定一个序列 $S$ ，其最长不下降子序列 $S^{'}$ 是原序列中的如下子序列：整个子序列 $S^{'}$ 单调不降，并且是序列中最长的单调不降子序列。例如，给定序列 $S = [11, 12, 13, 9, 8, 17, 19]$ ，其最长不下降子序列为 $S^{'} = [11, 12, 13, 17, 19]$ ，长度为 $5$ 。

输入格式

第一行包含两个正整数 $n, m$ ，表示节点数和边数。

第二行包含 $n$ 个正整数 $A_1, A_2, \dots A_n$ ，表示节点 $1$ 到 $n$ 的点权。

之后 $m$ 行每行包含两个正整数 $u_i, v_i$ ，表示第 $i$ 条边连接节点 $u_i$ 和 $v_i$ ，方向为从 $u_i$ 到 $v_i$ 。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

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

样例输出 #2

样例 #3

样例输入 #3

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

样例输出 #3

提示

数据规模与约定

子任务	分值	$n\le$	$A_i \le$	特殊约定
$1$	$30$	$10^3$	$10$	输入的图是一条链
$2$	$30$	$10^5$	$2$	无
$3$	$40$	$10^5$	$10$	无

对全部的测试数据，保证 $\leq n \leq 10^5$ ， $\leq m \leq 10^5$ ， $\leq A_i \leq 10$ 。

解题思路

提示：这是一道对初学者来说比较有难度的图上 dp，不理解的话可以在草稿纸上模拟一下，这样会更易懂一些。

看到题目，肯定是图论+dp的题。看到“路径上的经过节点的先后顺序”这句话，就知道要用拓扑排序。

然后，根据拓扑序，对每条边进行动态规划。但直接设 $f [i]$ 表示以 $i$ 结尾的 LIS 长度，每遇到一条边就更新一次。这样时间复杂度是 $O (nm)$ 的，会超时。

然后观察题目的“弱点”： $\le A[i] \le 10$ ，这么小？于是，第二种 LIS 思路来了：设 $f [i] [j]$ 表示从某处到点 $i$ ，结尾数为 $j$ 的LIS长度。

然后转移来了（重点）：对于 $v$ 的某个前驱节点 $u$ ：

将点 $v$ 加到点 $u$ 的 LIS 后面。 $f[v][A[i]]=max\{f[u][i]+1, f[v][A[i]]\}$ ，其中 $\le i \le A[u]$
用 $u$ 替换点 $v$ ，也可能得到更优的答案。 $f[v][i]=max\{f[u][i], f[v][i]\}$ ，其中 $\le i \le10$ 。

最后答案：所有 $f [i] [j]$ 的最大值。保证 $\le i \le n, 1 \le j \le 10$ 。

AC Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 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 ++) cin >> A[i];for(int u, v, i = 1; i <= m; i ++){cin >> u >> v;G[u].push_back(v);++ ind[v]; // 入度+1}queue <int> Q; // 拓扑排序的队列for(int i = 1; i <= n; i ++){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 ++){f[v][A[v]] = max(f[u][i] + 1, f[v][A[v]]);}for(int i = 1; i <= 10; i ++){f[v][i] = max(f[u][i], f[v][i]);}}}// 求所有答案的最大值int maxn = -1e9;for(int i = 1; i <= n; i ++){for(int j = 1; j <= 10; j ++) maxn = max(maxn, f[i][j]);}cout << maxn << '\n';
}signed main()
{ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);solve();return 0;
}