怪盗基德的滑翔翼

GitHub跳转原题关系图返回列表

题意与原解析均从本地 OpenJudge 缓存迁移。

OJ: noi_openjudge

题目 ID: ch0206-4977

难度:未知

标签:

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

完整题面见同目录的 problem.md。

思路

本题目就是lis,所以没有什么好讲的

f[i]=max(f[j]+1,1)  j<i∧aj<ai f[i] = max(f[j]+1,1) \; j < i \land a_j < a_i

注意正反算两次

代码

cpp
/* author: Rainboy email: rainboylvx@qq.com  time: 2022年 03月 03日 星期四 14:19:40 CST */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5,maxe = 1e6+5; //点与边的数量
int n,m;
int f1[maxn]; 
int a[maxn];

int main() {
    int t;
    cin>>t;
    while (t--) {
        std::cin >> n;
        for(int i = 1;i <= n ;++i ) // i: 1->n
        {
            cin >> a[i];
        }
        int ans = 0;
        //从左向右
        for(int i =1;i<=n;i++) {
            f1[i] = 1;
            for(int j =1;j<i;j++) {
                if( a[j] > a[i] && f1[j] + 1 > f1[i])
                {
                    f1[i] = f1[j]+1;
                    ans = max(ans,f1[i]);
                }
            }
        }
        //从右向左
        for(int i =n;i>=1;i--){
            f1[i] = 1;
            for(int j =n;j>i;j--){
                if( a[j] > a[i] && f1[j] + 1 > f1[i])
                {
                    f1[i] = f1[j]+1;
                    ans = max(ans,f1[i]);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

复杂度

总结