题目描述

blablabla

样例

blablabla

思路

条件1：每次所浏览景点的编号都要大于前一个浏览景点的编号，即选择的是数组的子序列
条件2：一旦开始下山，就不再向上走了，即选择的子序列都是先增后减
对于a[i]，以a[i]为最高点的情况，本质就是以a[i]为终点的正序LIS，和以a[i]为终点的逆序LIS

算法1

(动态规划解LIS) $O(n^2)$

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N], g[N], a[N];
int n;

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ ) {
        f[i] = 1;
        for (int j = 0; j < i; j ++ ) {
            if (a[i] > a[j]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }

    for (int i = n; i; i -- ) {
        g[i] = 1;
        for (int j = n; j > i; j -- ) {
            if (a[i] > a[j]) {
                g[i] = max(g[i], g[j] + 1);
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) {
        res = max(res, f[i] + g[i] - 1);
    }

    printf("%d\n", res);

    return 0;
}

算法2

(贪心+二分做LIS) $O(n^2)$

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N], g[N], a[N], q[N];
int n;

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    q[0] = -1;
    int len = 0;
    for (int i = 1; i <= n; i ++ ) {
        int l = 0, r = len;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        q[l + 1] = a[i];
        f[i] = l + 1;
    }

    len = 0;
    for (int i = n; i; i -- ) {
        int l = 0, r = len;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        q[l + 1] = a[i];
        g[i] = l + 1;
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) {
        res = max(res, f[i] + g[i] - 1);
    }

    printf("%d\n", res);

    return 0;
}