108叶先毅是个小蒟蒻

用户名：dotcpp0787179

访问量：92

签　名：

榜二别卷了！

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

　　自我简介：

那是纳西妲吗？

TA的其他文章

必备技法--高精加//vector数组版 + string版
浏览：10

必备技法--高精度乘法//vector版
浏览：7

dfs--字符转数存状态//[LETTERS]
浏览：10

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

dp--最长上升子序列模型//闫氏dp法[登山] -同一个点为结尾的最长上升下降和

　　作者: 108叶先毅是个小蒟蒻　　　　发表时间：2024-09-17 00:47:33 浏览：10　|　评论：1　

原题链接：登山

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

###### 题意 可以沿途参观景点 也就是 除了上山 下山也有 即
##### 以一个景点为参考系 向下加向上沿途景点数量最多的答案
###### 换句话说 就是 假设现在走到了k点 那么就是 上山方向以k结尾的最长上升子序列 加上 下山方向以k结尾的最长下降子序列 和 就是答案拉 是不是很简单
###### Code:
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long  // 个人习惯 有备无患
using namespace std;
const int N = 1100;
int n , a[N] , f[N] , g[N];  //a为提给数据数组 f , g为动态规划数组
int ans; // 记录答案

signed main()
{
    cin >> n;
    for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];

for (int i = 1 ; i <= n ; i ++ ) 
    {
        f[i] = 1; //初始化为1 自身也有一个景点 也是 答案
        for (int j = 1 ; j < i ; j ++ ) 
            if (a[i] > a[j]) f[i] = max(f[i] , f[j] + 1); //动态转移 最大上升子序列
    }

for (int i = n ; i >= 1 ; i --) 
    {
        g[i] = 1; 
        for (int j = n ; j > i ; j --) 
            if (a[i] > a[j]) g[i] = max(g[i] , g[j] + 1); //状态转移 反向最大上升子序列
    }

for (int i = 1 ; i <= n ; i ++ ) ans = max(ans , f[i] + g[i] - 1); //一定要 减一 因为f和g都被初始化为1 也就是 最后答案统计的时候 每个起点都是 统计了两次 故需要减一

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

0.0分

2 人评分

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

　　评论区

109徐守佳

/ ￣￣￣＼　 
|　ー　ー \　 
|　 ◉　◉ |   / ￣￣￣￣￣￣＼
\ 　 ▱　 / ∠ 不要卷了，             \ 
  ＼       イ      \         叶xy !!!    /
 ／　   　＼     \______________/
/　|　　  \ \　 
|　|　　　 | |

2024-09-17 13:52:39

108叶先毅是个小蒟蒻

TA的其他文章

你可能喜欢

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

众数问题（C++代码）

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

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

简单的a+b （C语言代码）

dp--最长上升子序列模型//闫氏dp法[登山] -同一个点为结尾的最长上升下降和

评论区

精彩推荐

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

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

不容易系列2 （C语言代码）

字符串对比（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

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

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

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

数列问题（C语言代码）

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

108叶先毅是个小蒟蒻

TA的其他文章

你可能喜欢

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

众数问题 （C++代码）

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

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

简单的a+b （C语言代码）

dp--最长上升子序列模型//闫氏dp法[登山] -同一个点为结尾的最长上升下降和

评论区

精彩推荐

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

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

不容易系列2 （C语言代码）

字符串对比 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

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

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

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

数列问题 （C语言代码）

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

众数问题（C++代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

　　评论区

字符串对比（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

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

数列问题（C语言代码）