秋招算法题——怪盗基德的滑翔翼

文章目录

题目描述

思路分析

注意点

• 只能从高到低
• 方向一旦选择了，就确定了

问题转换

• 一旦确定了方向和起点后，就变为求以出发点为结尾的最长上升子序列是多少
• 相当于同时确定两遍最长上升子序列，分别是不同节点作为结尾。

思维误区

• 这里并不是只能跳相邻的，可以跳跃着来，原来的思路有问题，原来的思路仅仅只能相邻的跳跃

实现代码

#include <iostream>
#include <algorithm>

using namespace std;

const int K = 110;
const int N = 110;
const int H = 12000;
int h[H];
int f[H];

int main() {
    int k;
    cin>>k;
    while(k --){
        int n = 0;
        cin>>n;
        for(int i = 1;i <= n;i ++){
            cin>>h[i];
        }
        int res = 0;
        for (int i = 1; i <= n; ++i) {

            f[i] = 1;
            // 左侧最长上升子序列
            for (int j = 1; j < i; ++j) {
                if(h[j] < h[i])
                    f[i] = max(f[i], f[j] + 1);
            }
            res = max(res, f[i]);
        }

        for (int i = n; i >= 1; -- i) {
            f[i] = 1;
            // 右侧最长上升子序列
            for (int k = n; k > i; --k) {
                if (h[k] < h[i])
                    f[i] = max(f[i], f[k] + 1);
                res = max(res, f[i]);
            }
        }

        cout<<res<<endl;

    }

    return 0;
}

思路总结

• 将这个问题分解为两个最长上升子序列问题，之前没有做过最长上升子序列，但是意识到了，代码结构和最后的代码比较相似。
• 自己之前没有做过最长上升子序列问题，这里学了一下，发现两层循环的上升子序列的代码，思路还是很巧妙的。