C++---最长上升子序列模型---登山（每日一道算法2023.2.28）

news/2024/4/19 10:11:07/文章来源:https://blog.csdn.net/SRestia/article/details/129253950

注意事项：
本题为"线性dp—最长上升子序列的长度" 和 “最长上升子序列模型—怪盗基德的滑翔翼” 的扩展题，所以dp思路这里就不再赘述。

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

输入格式
第一行包含整数N，表示景点数量。
第二行包含N个整数，表示每个景点的海拔。

输出格式
输出一个整数，表示最多能浏览的景点数。

数据范围
2≤N≤1000

输入:
8
186 186 150 200 160 130 197 220

输出：
4

#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010;
int w[N], f1[N], f2[N];
int n;//最长上升子序列模板，(int* f)是引用arr
void lis(int* f)
{for (int i = 1; i<=n; i++) {f[i] = 1;for (int j = 1; j<i; j++) {if (w[j] < w[i]) f[i] = max(f[i], f[j]+1);}}
}int main ()
{//接收数据cin >> n;for (int i = 1; i<=n; i++) cin >> w[i];//求两遍，一次最长上升子序列，一次最长下降子序列lis(f1);reverse(w+1, w+n+1);lis(f2);//把每个峰值点的上升和下降加在一起，算所有点作为峰值的max即可int x = 0;for (int i = 1; i<=n; i++) x = max(x, f1[i]+f2[n-i+1]); //这里因为下降子序列是反着求的，所以下标也是需要反着来cout << x-1 << endl;return 0;
}