yxy

用户名：dotcpp0787179

访问量：497

签　名：

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

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

　　自我简介：

我不会

TA的其他文章

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

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

你可能喜欢

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

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

　　作者: yxy　　　　发表时间：2024-09-17 00:47:33 浏览：27　|　评论：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

yxy

TA的其他文章

你可能喜欢

单词个数统计（C++代码）

上车人数（C语言代码）

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

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

C二级辅导-公约公倍（C语言代码）

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

评论区

精彩推荐

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

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

简单的for循环

WU-链表数据求和操作（C++代码）

WU-小九九（C++代码）

Cylinder （C语言描述+详细分析）

Tom数（C语言代码）

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

C语言训练-排序问题<1> （C语言代码）

小O的乘积（C++代码）

yxy

TA的其他文章

你可能喜欢

单词个数统计 （C++代码）

上车人数 （C语言代码）

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

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

C二级辅导-公约公倍 （C语言代码）

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

评论区

精彩推荐

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

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

简单的for循环

WU-链表数据求和操作 （C++代码）

WU-小九九 （C++代码）

Cylinder （C语言描述+详细分析）

Tom数 （C语言代码）

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

C语言训练-排序问题<1> （C语言代码）

小O的乘积 （C++代码）

单词个数统计（C++代码）

上车人数（C语言代码）

C二级辅导-公约公倍（C语言代码）

　　评论区

WU-链表数据求和操作（C++代码）

WU-小九九（C++代码）

Tom数（C语言代码）

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

小O的乘积（C++代码）