首页 > 代码库 > Codeforces 490F Treeland Tour 树上的最长上升子序列
Codeforces 490F Treeland Tour 树上的最长上升子序列
题目链接:点击打开链接
题意:
给定n个点的树。
下面n个数表示点权。
下面n-1行给出树。
找一条链,然后找出这条链中的点权组成的最长上升子序列。
求:最长上升子序列的长度。
思路:
首先是维护一条链然后求答案,但是如果直接树形dp(记录每个点u,u往下递增和u往下递减的长度)会使序列是来回的,即递增和递减都在同一条链上。
枚举每个点作为子序列的开头,然后维护一条链进行LIS的nlogn做法。
import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; public class Main { int max(int x, int y) { return x > y ? x : y; } static int N = 6050; int[] a = new int[N], len = new int[N]; int n; int ans; ArrayList<Integer>[] G = new ArrayList[N]; int[] Stack = new int[N]; int top; void find(int u, int fa) { int pos = -1, val = -1; if(a[u]>Stack[top-1]){ pos = -2;//-2表示新加了一个元素 Stack[top++] = a[u]; ans = max(ans, top); } else { int l = 0, r = top-1, siz = 0; while(l <= r){ int mid = (l+r)>>1; if(Stack[mid] < a[u]) l = mid+1; else { r = mid-1; siz = mid; } } pos = siz; val = Stack[siz]; Stack[pos] = a[u]; } for(int i = 0; i < G[u].size(); i++){ int v = G[u].get(i); if(v == fa)continue; find(v, u); } if(pos != -1){ if(pos == -2)top--; else { Stack[pos] = val; } } } void solve(int u) { for(int i = 0; i < G[u].size(); i++){ int v = G[u].get(i); top = 0; Stack[top++] = a[u]; find(v, u); } } void input() { n = cin.nextInt(); for (int i = 1; i <= n; i++) { G[i] = new ArrayList(); a[i] = cin.nextInt(); } for (int i = 1, u, v; i < n; i++) { u = cin.nextInt(); v = cin.nextInt(); G[u].add(v); G[v].add(u); } } public void work() { input(); ans = 1; for (int i = 1; i <= n; i++) solve(i); out.println(ans); } Main() { cin = new Scanner(System.in); out = new PrintWriter(System.out); } public static void main(String[] args) { Main e = new Main(); e.work(); out.close(); } public Scanner cin; public static PrintWriter out; }
Codeforces 490F Treeland Tour 树上的最长上升子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。