yxy

用户名：dotcpp0787179

访问量：497

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	976
经　　验	3389
参赛次数	3
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：38

你可能喜欢

dp--最长上升子序列模型//闫氏dp法[怪盗基德的滑翔翼] -正反取最大

　　作者: yxy　　　　发表时间：2024-09-17 00:03:58 浏览：25　|　评论：1　

原题链接：怪盗基德的滑翔翼

# 最长上升子序列模型 闫氏dp法
###### 最长上升子序列基础题模型 链接 ：[最长上升子序列模板题](https://www.dotcpp.com/oj/problem3050.html "最长上升子序列模板题")
###### 最长上升子序列基础题题解 链接 ： [最长上升子序列模板题 题解](https://blog.dotcpp.com/a/106388 "最长上升子序列模板题 题解")

![](/image_editor_upload/20240917/20240917120105_60391.jpg)

###### 本题的思路很简单 题目所说的 怪盗基德可以从任一位置开始 也就是 题目所给的顺序并不是严格顺序 可以倒序进行
###### 说到这里了 大家都知道了 可以进行两次取最长上升子序列 求两次的最大值就好了 是不是很简单
##### 不知道怎么求最长上升子序列的同学可以移步上面的链接 基础题解

###### Code：
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int t;
int a[110] , f[110];
signed main()
{
    ios::sync_with_stdio(false); //取消输入输出流
    cin >> t;

int ans ;  // 记录答案；；
    while (t --) 
    {
        int  n;
        cin >> n;
        ans = 0; // 每次都要归零 不然会影响一下组 测试点
        for (int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;

for (int i = 1 ; i <= n ; i ++ )   //正向最长上升子序列
        {   
            f[i] = 1;       //每个f[i] 都是一个楼 也是最低的答案 1
            for (int j = 1 ; j < i ; j ++ ) 
                if (a[i] > a[j]) f[i] = max(f[i] , f[j] + 1);
            
            ans = max(ans , f[i]);   //更新答案
        }

for (int i = n ; i >= 1 ; i -- )  //反向最长上升子序列
        {
            f[i] = 1;   //这里也需要初始值为1
            for (int j = n ; j > i ; j -- )
                if (a[i] > a[j]) f[i] = max(f[i] , f[j] + 1);

ans = max(ans , f[i]);      //更新答案
        }

cout << ans << endl;
    }
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

109徐守佳

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⠀⠀⣀⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀⠛⠿⠿⣿⠃⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀⠀⠙⢿⡇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇⠀⠀⠀⠀⠀
⠀⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇⠀⠀⠀⠀⠀⠀
⠀⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀

2024-09-17 00:40:01

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

Biggest Number (错误代码时间超限制)

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

矩阵乘法（C++代码）

dp--最长上升子序列模型//闫氏dp法[怪盗基德的滑翔翼] -正反取最大

评论区

精彩推荐

最小公倍数（C语言代码）

C语言训练-求函数值（C语言代码）

C语言训练-尼科彻斯定理（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【计算两点间的距离】（C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

Hello, world! （C语言代码）

The 3n + 1 problem （C语言代码）

程序员的表白（C语言代码）

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

Biggest Number (错误代码时间超限制)

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

矩阵乘法 （C++代码）

dp--最长上升子序列模型//闫氏dp法[怪盗基德的滑翔翼] -正反取最大

评论区

精彩推荐

最小公倍数 （C语言代码）

C语言训练-求函数值 （C语言代码）

C语言训练-尼科彻斯定理 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【计算两点间的距离】 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

Hello, world! （C语言代码）

The 3n + 1 problem （C语言代码）

程序员的表白 （C语言代码）

矩阵乘法（C++代码）

　　评论区

最小公倍数（C语言代码）

C语言训练-求函数值（C语言代码）

C语言训练-尼科彻斯定理（C语言代码）

【计算两点间的距离】（C语言代码）

程序员的表白（C语言代码）