codevs3955最长严格上升子序列
2024-09-08 09:52:55
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
给一个数组a1, a2 ... an,找到最长的上升降子序列ab1<ab2< .. <abk,其中b1<b2<..bk。
输出长度即可。
输入描述 Input Description
第一行,一个整数N。
第二行 ,N个整数(N < = 1000000)
输出描述 Output Description
输出K的极大值,即最长不下降子序列的长度
样例输入 Sample Input
5
9 3 6 2 7
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
n<=1000000
为了方便大家调试,数据名称已被修改——THREE
【思路】
n^2算法一定超时。
考虑....nlogn的算法。
dp[i]表示长度为i的上升序列的最后一个最小的数。
重点是最小的。只有最小才能扩展更多的数。
比如
2
4
3
1
图复制不上....1 2 3 4 表示序号,高度表示这个序号代表的数的大小,越高越大。
发现1 2 上升序列长度为2, 3 4序列长度也为2 那么dp[2] 是2还是4呢,(2,4表示是序号啊)
应该是4,因为4比2小 能扩展加入的数更多。
【code】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=0x3f3f3f3f;
int n,a[],dp[];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
memset(dp,0x3f,sizeof(dp));
for(int i=;i<=n;i++)
{
int p=upper_bound(dp+,dp+n+,a[i])-dp;
if(a[i]!=dp[p-])//严格上升序列
dp[p]=a[i];
}
for(int i=;i<=n+;i++)
{
if(dp[i]==maxn)
{
printf("%d\n",i-);
return ;
}
}
return ;
}
最新文章
- nginx缓冲区优化
- 国密SM4对称算法实现说明(原SMS4无线局域网算法标准)
- 用php随机生成福彩双色球号码的2种方法
- SendEmail语法
- JavaScript的事件对象_其他属性和方法
- Codeforces Round #326 (Div. 2) A. Duff and Meat 水题
- poj2828
- spring jdbctemplate调用procedure(返回游标)
- SRM 406(1-250pt, 1-500pt)
- hdu 5115 Dire Wolf(区间dp)
- DataTable转换实体类
- IOS 新消息通知提示-声音、震动
- iOS 之 手势
- AutoCAD中的扩展字典及扩展记录(C#)
- ActiveMq实例
- spacemacs conf
- Appium appium 安装不了
- gunicorn配置文件
- 【大数据系列】使用api修改hadoop的副本数和块大小
- golang应用打包成docker镜像