题目背景对应的选择、判断题试题 - GESP 七级样题C 组 - 洛谷有题题目描述小杨有个包含 n 个节点 m 条边的有向无环图其中节点的编号为 1 到 n。对于编号为 i 的节点其权值为 Ai​。对于图中的一条路径根据路径上的经过节点的先后顺序可以得到一个节点权值的序列小杨想知道图中所有可能序列中最长不下降子序列的最大长度。注给定一个序列 S其最长不下降子序列 S′ 是原序列中的如下子序列整个子序列 S′ 单调不降并且是序列中最长的单调不降子序列。例如给定序列 S[11,12,13,9,8,17,19]其最长不下降子序列为 S′[11,12,13,17,19]长度为 5。输入格式第一行包含两个正整数 n,m表示节点数和边数。第二行包含 n 个正整数 A1​,A2​,…An​表示节点 1 到 n 的点权。之后 m 行每行包含两个正整数 ui​,vi​表示第 i 条边连接节点 ui​ 和 vi​方向为从 ui​ 到 vi​。输出格式输出一行一个整数表示答案。输入输出样例输入 #1复制5 4 2 10 6 3 1 5 2 2 3 3 1 1 4输出 #1复制3输入 #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复制4输入 #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复制4说明/提示数据规模与约定子任务分值n≤Ai​≤特殊约定13010310输入的图是一条链2301052无34010510无对全部的测试数据保证 1≤n≤1051≤m≤1051≤Ai​≤10。代码实现#include iostream #include vector #include queue #include algorithm using namespace std; const int MAXA 10; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint A(n 1); for (int i 1; i n; i) { cin A[i]; } vectorvectorint g(n 1); vectorint in(n 1, 0); for (int i 1; i m; i) { int u, v; cin u v; g[u].push_back(v); in[v]; } vectorvectorint dp(n 1, vectorint(MAXA 1, 0)); queueint q; int ans 0; for (int i 1; i n; i) { int w A[i]; dp[i][w] 1; ans max(ans, 1); if (in[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); vectorint pre(MAXA 1, 0); pre[0] 0; for (int val 1; val MAXA; val) { pre[val] max(pre[val - 1], dp[u][val]); } for (int v : g[u]) { int wv A[v]; vectorint tmp dp[u]; int newlen pre[wv] 1; tmp[wv] max(tmp[wv], newlen); for (int k 1; k MAXA; k) { if (tmp[k] dp[v][k]) { dp[v][k] tmp[k]; ans max(ans, dp[v][k]); } } in[v]--; if (in[v] 0) q.push(v); } } cout ans endl; return 0; }