本文主要是介绍【算法】登山（线性DP，最长上升），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。
队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？
输入格式
第一行包含整数N，表示景点数量。
第二行包含N个整数，表示每个景点的海拔。
输出格式
输出一个整数，表示最多能浏览的景点数。
数据范围
2≤N≤1000
8
186 186 150 200 160 130 197 220
输出样例：
4思路
先上山后下山，题意是寻找点 i 之前的最大上升子序列与点 i 之后的最大下降子序列。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
int n;
int h[N];
int u[N],d[N];int main()
{cin >> n;for(int i = 1; i <= n; i ++) cin >> h[i];for(int i = 1; i <= n; i ++)// 上升{u[i] = 1;for(int j = 1; j < i; j ++){if(h[j] < h[i]) u[i] = max(u[i],u[j] + 1);}}for(int i = n; i ; i --)// 下降{d[i] = 1;for(int j = n; j > i; j --){if(h[j] < h[i]) d[i] = max(d[i],d[j] + 1);}}int res = 0;for(int i = 1; i <= n; i ++){res = max(u[i] + d[i] - 1,res);}cout << res << endl;
}| 难度：简单 |
| 时/空限制：1s / 64MB |
| 总通过数：17656 |
| 总尝试数：36738 |
| 来源： 《信息学奥赛一本通》第六届北京大学程序设计大赛暨ACM/ICPC选拔赛 |
| 算法标签 DP 线性DP 最长上升子序列 |
题目来自： AcWing 1014. 登山 - AcWing
这篇关于【算法】登山（线性DP，最长上升）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
