专栏首页数据结构与算法1576 最长严格上升子序列

1576 最长严格上升子序列

1576 最长严格上升子序列

 时间限制: 1 s

 空间限制: 256000 KB

 题目等级 : 黄金 Gold

题解

题目描述 Description

给一个数组a1, a2 ... an,找到最长的上升降子序列ab1<ab2< .. <abk,其中b1<b2<..bk。

输出长度即可。

输入描述 Input Description

第一行,一个整数N。

第二行 ,N个整数(N < = 5000)

输出描述 Output Description

输出K的极大值,即最长不下降子序列的长度

样例输入 Sample Input

5

9 3 6 2 7

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

【样例解释】

最长不下降子序列为3,6,7

裸题!

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int MAXN=10001;
 5 int a[MAXN];
 6 int f[MAXN];//长度 
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     for(int i=1;i<=n;i++)
12     scanf("%d",&a[i]);
13     for(int i=1;i<=n;i++)
14     f[i]=1;
15     for(int i=1;i<=n;i++)
16     {
17         for(int j=1;j<i;j++)
18         {
19             if(a[i]>=a[j])
20             {
21                 //f[i]=max(f[j]+1,f[i]);
22                 f[i]=f[j]+1;
23             }
24         }
25     }
26     printf("%d",f[n]);
27     return 0;
28 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ4337: BJOI2015 树的同构(hash 树同构)

    attack
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack
  • 1008 选数 2002年NOIP全国联赛普及组

    1008 选数 2002年NOIP全国联赛普及组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 ...

    attack
  • BZOJ4337: BJOI2015 树的同构(hash 树同构)

    attack
  • 程序员面试金典 - 面试题 10.10. 数字流的秩(map/树状数组)

    假设你正在读取一串整数。每隔一段时间,你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。

    Michael阿明
  • XMU oj Problem List

    注意不要有不必要的输出,比如"请输入 a 和 b 的值: ",示例代码见隐藏部分。

    glm233
  • 【CodeForces 730H】Car Repair Shop

    模拟,先看从s[i]时刻开始修理,和之前i-1个是否冲突。如果冲突,就枚举每个s[j]+d[j]时刻开始,看是否冲突,再从中选择最小的时刻。

    饶文津
  • 生成1~n的排列(模板),生成可重集的排列(对应紫书P184, P185)

    _DIY
  • 数组的简单练习题

    1.将一个给定的整型数组转置输出, 例如: 源数组,1 2 3 4 5 6 转置之后的数组,6 5 4 3 2 1

    阮键
  • 2016计蒜之道复赛 百度地图的实时路况(Floyd 分治)

    首先一个结论:floyd算法的正确性与最外层\(k\)的顺序无关(只要保证是排列即可)

    attack

扫码关注云+社区

领取腾讯云代金券