一个人的巴黎

用户名：uq_36478041918

访问量：14988

签　名：

等　　级
排　　名	105
经　　验	8303
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

蓝桥杯2018年第九届真题-日志统计
浏览：136

蓝桥杯2018年第九届真题-全球变暖
浏览：205

蓝桥杯2018年第九届真题-乘积最大
浏览：224

你可能喜欢

求最长不下降序列(序列型动态规划

　　作者: 一个人的巴黎　　　　发表时间：2022-02-12 16:30:34 浏览：581　|　评论：0　

原题链接：信息学奥赛一本通T1259-求最长不下降序列

```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int b[201];
int dp[201];
int path[201];//path[]数组存储最长上升子序列的每一个下标
int res=-1;
int k;//终止位置
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>b[i];
    for(int i=0;i<n;i++){//最后一步dp[i]:以b[i]结尾的最长上升子序列的长度
        dp[i]=1;//情况1：最长上升子序列就是b[i]本身
        path[i]=0;
        for(int j=0;j<i;j++){//情况2：以b[j](j<i)结尾的最长上升子序列的长度，
        //加上b[i]
            if(b[j]<=b[i]&&dp[i]<dp[j]+1){
               dp[i]=dp[j]+1;//取两种情况的较大值
            }
        }
        if(dp[i]>res){
            res=dp[i];//不知道到哪个位置i结束，所以维护一个最大值
            k=i;//记录最长上升子序列的终止位置下标
        }
    }
    int q=0,m=res,i=k-1;
    path[q++]=k;//终止坐标入栈
    while(m>1){
        if(dp[i]==m-1&&b[i]<=b[k]){//当子序列的长度-1并且此时数小于上一个数
            path[q++]=i;//下标入栈
            k=i;//保存上一个位置下标
            m--;//子序列的长度-1
        }
        i--;
    }
    cout<<"max="<<res<<endl;
    for(int i=q-1;i>0;i--)//逆序输出
        cout<<b[path[i]]<<" ";
    cout<<b[path[0]]<<endl;
    return 0;
}
```

0.0分

2 人评分

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

一个人的巴黎

TA的其他文章

你可能喜欢

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

蛇行矩阵（C++代码）（预生成结果以节省每次生成的时间）

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

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

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

求最长不下降序列(序列型动态规划

评论区

精彩推荐

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

C语言考试练习题_排列（C语言代码）

【亲和数】（C语言代码）

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

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

【矩阵】（C++代码）

1908题解

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

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

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

一个人的巴黎

TA的其他文章

你可能喜欢

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

蛇行矩阵 （C++代码）（预生成结果以节省每次生成的时间）

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

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

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

求最长不下降序列(序列型动态规划

评论区

精彩推荐

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

C语言考试练习题_排列 （C语言代码）

【亲和数】 （C语言代码）

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

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

【矩阵】 （C++代码）

1908题解

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

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

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

蛇行矩阵（C++代码）（预生成结果以节省每次生成的时间）

　　评论区

C语言考试练习题_排列（C语言代码）

【亲和数】（C语言代码）

【矩阵】（C++代码）