侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-10 / 0 评论 / 0 点赞 / 84 阅读 / 535 字
温馨提示:
本文最后更新于 2023-02-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1014. 登山 - AcWing题库


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

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

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

输入格式

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

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

输出格式

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

数据范围

2N10002 \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);
    }
}
0

评论区