五一到了,ACM队组织大家去登山观光,队员们发现山上一共有N个景点,并且决定按照顺序来浏览这些景点,即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯,就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了。
队员们希望在满足上面条件的同时,尽可能多的浏览景点,你能帮他们找出最多可能浏览的景点数么?
输入格式
第一行包含整数N,表示景点数量。
第二行包含N个整数,表示每个景点的海拔。
输出格式
输出一个整数,表示最多能浏览的景点数。
数据范围
$2 \\le N \\le 1000$
输入样例:
8
186 186 150 200 160 130 197 220
输出样例:
4
算法1
(动态规划) $O(n^2)$
同时队员们还有另一个登山习惯,就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了。
由题目中这段话可以得知,题目要求最长上升子序列。
由于有登山、下山两种情况,我们考虑用类似怪盗基德的滑翔翼方法来做。
首先跑正反两遍的最长上升子序列。
记
- 正的最长上升子序列为 $f[ \ ]$
- 反的最长上升子序列为 $g[ \ ]$
最终遍历 $1$ 到 $n$ ,取最大的 $f[i] + g[i] - 1$ 即可。
原因:
因为 $i$ 为登山最高点也是下山开始点,所以我们把 $f[i]$ 和 $g[i]$ 加起来。
而 $i$ 点同时被算两次,所以减去 $1$。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n;
int h[N];
int f[N],g[N];
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&h[i]);
for(int i = 1;i <= n;i ++){
f[i] = 1;
for(int j = 1;j <= i;j ++){
if(h[i] > h[j]) f[i] = max(f[i],f[j] + 1);
}
}
for(int i = n;i >= 1;i --){
g[i] = 1;
for(int j = n;j >= i;j --){
if(h[i] > h[j]) g[i] = max(g[i],g[j] + 1);
}
}
int res = 0;
for(int i = 1;i <= n;i ++) res = max(res,f[i] + g[i] - 1);
printf("%d\n",res);
return 0;
}