本文主要是介绍Codeforces 490F Treeland Tour(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：Codeforces 490F Treeland Tour
类似于nlogn的递增上升子序列算法。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>using namespace std;
const int maxn = 6005;
const int inf = 0x3f3f3f3f;int N, R[maxn], D[maxn], ans = 0;
vector<int> g[maxn];void init () {scanf("%d", &N);for (int i = 1; i <= N; i++)scanf("%d", &R[i]);for (int i = 0; i < N; i++)D[i] = inf;int a, b;for (int i = 1; i < N; i++) {scanf("%d%d", &a, &b);g[a].push_back(b);g[b].push_back(a);}
}void dfs(int u, int f) {int idx = lower_bound(D, D + N, R[u]) - D;ans = max(ans, idx + 1);int tmp = D[idx];D[idx] = R[u];for (int i = 0; i < g[u].size(); i++) {if (g[u][i] == f) continue;dfs(g[u][i], u);}D[idx] = tmp;
}int main () {init();for (int i = 1; i <= N; i++)dfs(i, 0);printf("%d\n", ans);return 0;
}
这篇关于Codeforces 490F Treeland Tour(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
