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

测试信息如下：

总之谁能帮帮我！

P10379 [GESP202403 七级] 俄罗斯方块：你好！

xpg007：gǔn

代码在此

#include <bits/stdc++.h>
using namespace std;
struct node{
	int to, k;
};
vector<node> g[100001];
vector<int> v;
bool vis[100001];
int a[100001], dp[100001], rd[100001];
bool cmp(node x, node y){
	return x.k > y.k;
}
void dfs(int x){
	v.push_back(x);
	for (int i = 0; i < g[x].size(); i++)
		if (!vis[g[x][i].to]){
			vis[g[x][i].to] = true;
			dfs(g[x][i].to);
		}
}
int main(){
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back({v, a[v]});
		rd[v]++;
	}
	int root = 1;
	for (int i = 1; i <= n; i++){
		sort(g[i].begin(), g[i].end(), cmp);
		if (rd[i] == 0)
			root = i;
	}
	vis[root] = true;
	dfs(root);
	for (int i = 1; i <= n; i++)
		dp[i] = true;
	for (int i = 0; i < (v.size() - 1) / 2; i++)
		swap(v[i], v[v.size() - 1 - i]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < n; j++)
			if (v[i - 1] > v[j - 1])
				dp[i] = max(dp[i], dp[j] + 1);
	cout << dp[n];
	return 0;
}