1996:登山

总时间限制: 

5000ms

 

内存限制: 

131072kB

描述

五一到了，PKU-ACM队组织大家去登山观光，队员们发现山上一个有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入

Line 1： N (2 <= N <= 1000) 景点数
Line 2： N个整数，每个景点的海拔

输出

最多能浏览的景点数

样例输入

8
186 186 150 200 160 130 197 220

样例输出

4

来源

第六届北京大学程序设计大赛暨ACM/ICPC选拔赛

开始的时候认为是一个单纯的求最长不下降序列，结果WA了，回过头重新看了一下题，发现不仅仅要求上山的点，还要求下山的点。知道这一点就很容易求出来了。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define Max 1200
 6 int dis[Max],a[Max],dsi[Max];
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     for(int i=1;i<=n;i++)
12     {
13         scanf("%d",&a[i]);
14         dis[i]=dsi[i]=1;
15     }
16     for(int i=1;i<=n;i++)
17     {
18         int maxx=0;
19         for(int j=1;j<i;j++)
20             if(a[j]<a[i]&&dsi[j]>maxx)
21                 maxx=dsi[j];
22             dsi[i]=maxx+1;
23     }
24     for(int i=n-1;i>=1;i--)
25     {
26         int maxx=0;
27         for(int j=i+1;j<=n;j++)
28             if(a[j]<a[i]&&dis[j]>maxx)
29                 maxx=dis[j];
30         dis[i]=maxx+1;
31     }
32     int maxx=0;
33     for(int i=1;i<=n;i++)
34         maxx=max(maxx,dsi[i]+dis[i]-1);
35     printf("%d",maxx);
36     return 0;
37 }

View Code