🍑 算法题解专栏

---

🍑 洛谷 登山

登山

题目描述

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

输入格式

Line1:N(2<=N<=1000)景点数

Line2:N个整数，每个景点的海拔

输出格式

最多能浏览的景点数

样例 #1

样例输入 #1

8
186 186 150 200 160 130 197 220

样例输出 #1

4

---

🍑 题意（阅读理解）
① 按照编号递增的顺序来浏览 --> 子序列
② 相邻两个经典海拔不能相同 --> 严格递增/减
③ 一旦开始下降，就不能上升的 --> 先爬山 后下山

🤠 思路
① 取中点 k，求两边最大的递增递减的最长子序列长度 O(n^3)
② 预处理左右两边的最长上升子序列长度，O(n^2)

🍑 res = max( f[i] + g[i] -1) , 0 <= i < n
🍤 中间点算了两次，-1

👨‍🏫 注意数组下标对应的关系

import java.util.Scanner;public class Main
{static int N = 1010;static int[] w = new int[N];static int[] f = new int[N];static int[] g = new int[N];public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 1; i <= n; i++)w[i] = sc.nextInt();for (int i = 1; i <= n; i++){f[i] = 1;for (int j = 1; j < i; j++)if (w[i] > w[j])f[i] = Math.max(f[i], f[j] + 1);}for (int i = n; i > 0; i--){g[i] = 1;for (int j = n; j > i; j--)if (w[i] > w[j])g[i] = Math.max(g[i], g[j] + 1);}int res = 0;for (int i = 1; i <= n; i++)res = Math.max(res, f[i] + g[i] - 1);System.out.println(res);}
}