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选拔赛
- 分析：合唱队形的变式，跑两次最长上升子序列就可以了
- 代码：
- #include< cstdio >
- #include< iostream >
- using namespace std;
- int high[1001],line[1001],n,linb[1001],lina[1001],M=-1;
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;++i)
- {
- scanf("%d",&high[i]);
- line[i]=1;
- linb[i]=1;
- }
- for(int i=n-1;i>=1;--i)
- {
- int maxx=1;
- for(int j=i+1;j<=n;++j)
- {
- if(high[i]>high[j]&&line[j]+1>maxx)
- maxx=line[j]+1;
- }
- line[i]=maxx;
- }
- for(int i=2;i<=n;++i)
- {
- int maxx=1;
- for(int j=1;j
- {
- if(high[i]>high[j]&&linb[j]+1>maxx)
- maxx=linb[j]+1;
- }
- linb[i]=maxx;
- lina[i]=linb[i]+line[i]-1;
- M=max(M,lina[i]);
- }
- cout<<M;
- return 0;
- }