首页 > 代码库 > Laoj P1194 [hnoi97]最长不下降序列
Laoj P1194 [hnoi97]最长不下降序列
|
问题背景
|
|
动态规划入门-第13题
|
|
试题描述
|
|
设有整数序列b1,b2,b3,…,bm，若存在i1<i2<i3<…<in，且bi1<bi2<bi3<…<bin，则称 b1,b2,b3,…,bm中有长度为n的不下降序列bi1,bi2,bi3,…,bin。求序列b1,b2,b3,…,bm中所有长度(n)最大不下降子序列。例如3，18，7，14，10，12，23，41，16，24，其中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。
|
|
输入格式
|
|
第一行为n，表示n个数
第二行n个数 |
|
输出格式
|
|
最长不下降子序列的长度
|
|
输入示例
|
|
10
3 18 7 14 10 12 23 41 16 24 |
|
输出示例
|
|
6
|
|
注释说明
|
|
N小于5000
for each num <=maxint |
【分析】
dp入门，就是lis啦，不过这题目描述有点迷，看题目是不下降，看描述是上升，其实还是不下降，水题。
【代码】
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int n, a[5050], dp[5050], ans; 5 6 int main() { 7 cin >> n; 8 for (int i=1;i<=n;++i) 9 cin >> a[i]; 10 for (int i=1;i<=n;++i) { 11 dp[i]=1; 12 for (int j=i-1;j>0;--j) 13 if (a[j]<=a[i]) 14 dp[i]=max(dp[i], dp[j]+1); 15 } 16 for (int i=1;i<=n;++i) 17 ans=max(ans, dp[i]); 18 cout << ans << endl; 19 }
---恢复内容结束---
Laoj P1194 [hnoi97]最长不下降序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。