首页 / HTML / CodeforcesRound#279(Div.2)F.TreelandTour（lis+dfs）_html/css_WEB-ITnose

CodeforcesRound#279(Div.2)F.TreelandTour（lis+dfs）_html/css_WEB-ITnose

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#279(Div.2)F.TreelandTour（lis+dfs）_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5027字，纯文字阅读大概需要8分钟。

内容图文

题目链接：

huangjing


题意：告诉一个无向无环图，然后求在联通的路上的lis。

思路：枚举起点求lis 复杂度是n^2logn,貌似这复杂度对时间有点玄，估计是数据有点弱。。。

首先枚举起点，然后求lis，主要是用dfs求的，要用到回溯的思想，我觉得是只要更新了，就要保存那个操作，然后一旦这一次的搜索完成，那么就要立即回复g数组的值，因为有很多不同的路线，所以一条路走完后，就要回复以前的状态哦，免得影响另外一条路。。我觉得尽管他们都说是暴力，但是我觉得这个题还是蛮好的。。。

题目:

F. Treeland Tour

time limit per test

5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The "Road Accident" band is planning an unprecedented tour around Treeland. The RA fans are looking forward to the event and making bets on how many concerts their favorite group will have.

Treeland consists of n cities, some pairs of cities are connected by bidirectional roads. Overall the country has n?-?1 roads. We know that it is possible to get to any city from any other one. The cities are numbered by integers from 1 to n. For every city we know its valueri ? the number of people in it.

We know that the band will travel along some path, having concerts in some cities along the path. The band's path will not pass one city twice, each time they move to the city that hasn't been previously visited. Thus, the musicians will travel along some path (without visiting any city twice) and in some (not necessarily all) cities along the way they will have concerts.

The band plans to gather all the big stadiums and concert halls during the tour, so every time they will perform in a city which population is larger than the population of the previously visited with concert city. In other words, the sequence of population in the cities where the concerts will be held is strictly increasing.

In a recent interview with the leader of the "road accident" band promised to the fans that the band will give concert in the largest possible number of cities! Thus the band will travel along some chain of cities of Treeland and have concerts in some of these cities, so that the population number will increase, and the number of concerts will be the largest possible.

The fans of Treeland are frantically trying to figure out how many concerts the group will have in Treeland. Looks like they can't manage without some help from a real programmer! Help the fans find the sought number of concerts.

Input

The first line of the input contains integer n (2?≤?n?≤?6000) ? the number of cities in Treeland. The next line contains n integersr1,?r2,?...,?rn (1?≤?ri?≤?106), where ri is the population of the i-th city. The next n?-?1 lines contain the descriptions of the roads, one road per line. Each road is defined by a pair of integers aj, bj (1?≤?aj,?bj?≤?n) ? the pair of the numbers of the cities that are connected by thej-th road. All numbers in the lines are separated by spaces.

Output

Print the number of cities where the "Road Accident" band will have concerts.

Sample test(s)

input 

61 2 3 4 5 11 22 33 43 53 6

output

input 

51 2 3 4 51 21 32 43 5

output


代码： 

#include#include#include#include#include#include#include#include#include#define eps 1e-9#define ll long long#define INF 0x3f3f3f3fusing namespace std;priority_queue<int,vector,greater >Q;const int maxn=6000+10;struct Egde{    int next,to;}edge[maxn<<1];int g[maxn],val[maxn],head[maxn],cnt,n,ans,top;void add_edge(int x,int y){    edge[++cnt].to=y;    edge[cnt].next=head[x];    head[x]=cnt;}void dfs(int u,int top=0,int fa=0){     int tmp,pos;     if(top==0||val[u]>g[top])     {         pos=++top;         tmp=g[top];         g[top]=val[u];         ans=max(ans,top);     }     else     {         pos=lower_bound(g+1,g+1+top,val[u])-g;         tmp=g[pos];         g[pos]=val[u];     }     for(int i=head[u];~i;i=edge[i].next)     {         int v=edge[i].to;         if(v!=fa)            dfs(v,top,u);     }     g[pos]=tmp;}int main(){    int x,y;    while(~scanf("%d",&n))    {        ans=cnt=0;        memset(head,-1,sizeof(head));        memset(g,-1,sizeof(g));        for(int i=1;i<=n;i++)            scanf("%d",&val[i]);        for(int i=1;i<=n-1;i++)        {            scanf("%d%d",&x,&y);            add_edge(x,y);            add_edge(y,x);        }        for(int i=1;i<=n;i++)            dfs(i);        printf("%d\n",ans);    }    return 0;}

内容总结

以上是互联网集市为您收集整理的CodeforcesRound#279(Div.2)F.TreelandTour（lis+dfs）_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#279(Div.2)F.TreelandTour（lis+dfs）_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/399392.html

来源：【匿名】