连接:http://acm.nyist.net/JudgeOnline/problem.php?pid=214
单调递增子序列(二)
时间限制:1000 ms | 内存限制:65535 KB
难度:4
给定一整型数列{a1,a2...,an}(0<n<=100000),找出单调递增最长子序列,并求出其长度。
如:1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13,长度为5。
每组测试数据的第一行是一个整数n表示序列中共有n个整数,随后的下一行里有n个整数,表示数列中的所有元素.每个整形数中间用空格间隔开(0<n<=100000)。
数据以EOF结束 。
输入数据保证合法(全为int型整数)!
7 1 9 10 5 11 2 13 2 2 -1
5 1
#include<stdio.h> const int M=100010; int mask[M/2]; int date,max; void gg(int l,int r) { if(r==l) { mask[r]=date; return; } int mid=(l+r)>>1; if(date > mask[mid])gg(mid+1,r); else gg(l,mid); } int main() { // freopen("in.txt","r",stdin); int n,i,j; while(~scanf("%d",&n)) { max=1; scanf("%d",&date); mask[1]=date; for(i=2;i<=n;i++) { scanf("%d",&date); if(date>mask[max]) { max++; mask[max]=date; continue; } gg(1,max); } printf("%d\n",max); } return 0; }
相关推荐
南阳理工oj离线题库
南阳理工学院OJ第1版解题报告V1.0.pdf
南阳理工学院OJ_个人AC代码包(Java提交) 是Java初学者登堂入室的很好例子。
南阳理工学院stl练习场全部ac代码!
南阳理工ACM离线题库
哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案
OJ动态规划DP题目列表 POJ SOJ HDU 动态规划题目
山东理工大学2016级OJ进程,始于悦行,终于诚信。
西安理工大学学生在线实验系统编程题答案(超级详细)
基于Laravel 5.0的OJ题解网站 , 目前涵盖安科OJ,南阳OJ,杭电OJ ,北大OJ,浙大OJ.zip
这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 7 1 7 3 5 9 4 8 6 1 8 3 6 5 9 5 1 2 3 4 5 0 输出样例 4 4 5 提示 一,对输入...
算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于...
趣味题:柱状图排序 西安理工大学学生在线实验系统 oj
北航OJ上的动态规划题目整理,部分附代码
基于bootstrap对hustoj前端的二次改造
给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。
山东理工大学2016级OJ题目1833
杭电OJ题目分类的叙述,可以方便去学习去做。
在线OJ网址大全在线OJ网址大全在线OJ网址大全在线OJ网址大全
山东理工大学2016级OJ题目1834