Nowcoder 旅行青蛙的最短上升子序列板子题

一、 题意

一只青蛙当看的当前景点比前面看过的景点差的时候，青蛙就会说“不开心”为了避免这只青蛙说“不开心”，并且使青蛙看的景点尽量的多，所以他请你帮忙给他安排一条线路，使青蛙可以看到尽量多的景点，并且不走回头路。

第一行为一个整数n，表示景点的数量，接下来n行，每行1个整数，分别表示第i个景点的质量。

一个整数，表示青蛙最多可以看到几个景点。

二、解析

最长上升子序列板子题，顺便复习一下。

有用动态规划的O(n^2)方法和用贪心+二分的O(nlgn)方法，两个都可以的。

三、代码

• 动态规划

#include <iostream>
using namespace std;
const int maxn = 23333 + 5;
int n, a[maxn], dp[maxn];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    int ans = 0;
    for(int i = 1; i <= n; i ++) {
        dp[i] = 1;
        for(int j = 1; j < i; j ++) {
            if(a[i] >= a[j]) dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}

• 贪心+二分

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 23333 + 5, INF = 1 << 30;
int n, a[maxn], low[maxn];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    fill(low, low + n + 1, INF);
    int ans = 0;
    for(int i = 1; i <= n; i ++) {
        if(ans == 0 || a[i] >= low[ans]) low[++ ans] = a[i];
        else {
            int j = upper_bound(low + 1, low + n + 1, a[i]) - low;
            low[j] = a[i];
        }
    }
    cout << ans << endl;
}

四、归纳

• 动态规划的方法比较好理解，贪心+二分的方法比较快
• 最好记下来