P10287 [GESP Sample Problem Level 7] Longest Non-decreasing Subsequence

Related multiple-choice and true/false questions: .

Xiao Yang has a directed acyclic graph (DAG) with $n$ nodes and $m$ edges, where the nodes are numbered from $1$ to $n$. For the node with index $i$, its weight is $A_i$. For any path in the graph, following the order of nodes visited along the path gives a sequence of node weights. Xiao Yang wants to know, among all possible sequences in the graph, the maximum possible length of the longest non-decreasing subsequence. Note: Given a sequence $S$, its longest non-decreasing subsequence $S'$ is a subsequence of $S$ such that $S'$ is non-decreasing, and its length is as large as possible among all non-decreasing subsequences. For example, given $S = [11,12,13,9,8,17,19]$, its longest non-decreasing subsequence is $S' = [11,12,13,17,19]$, with length $5$.

The first line contains two positive integers $n, m$, representing the number of nodes and the number of edges. The second line contains $n$ positive integers $A_1, A_2, \dots A_n$, representing the node weights of nodes $1$ to $n$. Then $m$ lines follow, each containing two positive integers $u_i, v_i$, indicating that the $i$-th edge connects node $u_i$ to node $v_i$, directed from $u_i$ to $v_i$.

Output one line containing one integer, representing the answer.

### Constraints | Subtask | Points | $n \le$ | $A_i \le$ | Special Constraint | | :-: | :-: | :-: | :-: | :-: | | $1$ | $30$ | $10^3$ | $10$ | The input graph is a single chain. | | $2$ | $30$ | $10^5$ | $2$ | None. | | $3$ | $40$ | $10^5$ | $10$ | None. | For all testdata, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq m \leq 10^5$, and $1 \leq A_i \leq 10$. Translated by ChatGPT 5