108叶先毅是个小蒟蒻

用户名：dotcpp0787179

访问量：92

签　名：

榜二别卷了！

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

　　自我简介：

那是纳西妲吗？

TA的其他文章

dp--数字三角形模型系列//闫氏dp法
浏览：13

dp--最长上升子序列模型//闫氏dp法
浏览：8

dp--数字三角形模型//闫氏dp法[最低通行费]
浏览：8

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

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

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

　　作者: 108叶先毅是个小蒟蒻　　　　发表时间：2024-09-17 00:03:58 浏览：7　|　评论：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分

1 人评分

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

　　评论区

109徐守佳

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

2024-09-17 00:40:01

108叶先毅是个小蒟蒻

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

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

C语言训练-自守数问题（C语言代码） long long

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

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

评论区

精彩推荐

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

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

三角形（C++代码）递推

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

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

Tom数（C语言代码）

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

108叶先毅是个小蒟蒻

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

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

C语言训练-自守数问题 （C语言代码） long long

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

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

评论区

精彩推荐

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

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

三角形 （C++代码）递推

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

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

Tom数 （C语言代码）

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

C二级辅导-进制转换（C语言代码）

C语言训练-自守数问题（C语言代码） long long

　　评论区

三角形（C++代码）递推

Tom数（C语言代码）