yxy

用户名：dotcpp0787179

访问量：497

签　名：

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

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

　　自我简介：

我不会

TA的其他文章

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣
浏览：56

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

你可能喜欢

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

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

dp--最长上升子序列模型//闫氏dp法

　　作者: yxy　　　　发表时间：2024-09-16 02:18:42 浏览：32　|　评论：0　

原题链接：最长上升子序列

# dp基础入门 上升子序列模型
## 闫氏dp法
同系列基础dp算法链接：[dp--数字三角形模型](https://blog.dotcpp.com/a/106383 "dp--数字三角形模型")

![](/image_editor_upload/20240916/20240916021218_11548.png)

可以轻松的看出 每找到一个比当前数字要小的 就让 以上一个数字结尾的最长上升序列加上当前数字（也就是加一） 变成以当前数字为结尾的最长上升序列；
###### 那么我们可以简单的得出状态转移公式：
###### f[i] = max(f[i] , d[j] + 1);

下面就是ac时光：
###### Code:
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long  //个人习惯 有备无患
using namespace std; 
const int N = 10010;
int n , a[N];
int ans , f[N];

signed main()
{
    cin >> n;
    for (int i = 1 ; i <= n ; i ++ ) cin >> a[i] , f[i] = 1; //重要 先初始化f数组为一 因为每个数字自己也是一个 值为1 的子序列

for (int i = 1 ; i <= n ; i ++ ) 
    {
        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]); //再此更新最大的ans
    }

cout << ans << endl;

return 0;
}
```

# AC完此题后
###### 推荐最长上升子序列变形 链接 : [最长不下降子序列](https://www.dotcpp.com/oj/problem2124.html?sid=17555921&lang=1#editor "最长不下降子序列")
###### 借由此题 来看看自己掌握了多少把！

0.0分

1 人评分

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

yxy

TA的其他文章

你可能喜欢

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

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

C语言训练-邮票组合问题* （C语言代码）

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

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

dp--最长上升子序列模型//闫氏dp法

评论区

精彩推荐

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

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

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

WU-输出正反三角形（C++代码）

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

1012题解

大家好，我是验题君

1118（求助_已解决）

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

Hello, world! （C语言代码）

yxy

TA的其他文章

你可能喜欢

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

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

C语言训练-邮票组合问题* （C语言代码）

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

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

dp--最长上升子序列模型//闫氏dp法

评论区

精彩推荐

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

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

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

WU-输出正反三角形 （C++代码）

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

1012题解

大家好，我是验题君

1118（求助_已解决）

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

Hello, world! （C语言代码）

　　评论区

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

WU-输出正反三角形（C++代码）