【动态规划】登山「动态规划之LIS模型」

题目

1014. 登山 - AcWing题库

---

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式

第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式

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

数据范围

$2 \le N \le 1000$

输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

4

解题

方法一：动态规划

思路

本题抽象为求一个先上升后下降的最长子序列。

转换为对序列求一个正序的最长上升子序列、一个倒序的最长上升子序列，然后遍历每个点维护最长先上升后下降最长子序列即可。

模板：【动态规划】最长上升子序列。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        int[] f = new int[n], g = new int[n];
        for (int i = 0; i < n; ++i) {
            f[i] = 1;
            for (int j = 0; j < n; ++j) {
                if (a[j] < a[i]) f[i] = Math.max(f[i], f[j] + 1);
            }
        }
        int mx = 1;
        for (int i = n - 1; i >= 0; --i) {
            g[i] = 1;
            for (int j = n - 1; j > i; --j) {
                if (a[j] < a[i]) g[i] = Math.max(g[i], g[j] + 1);
            }
            mx = Math.max(mx, f[i] + g[i] - 1);
        }
        System.out.println(mx);
    }
}