动态规划|Codevs P3955 最长严格上升子序列(加强版)(nlogn求法) 动态规划|pascal

Codevs P3955 最长严格上升子序列(加强版)(nlogn求法) 表示看电脑看到头晕脑痛。。。哈欠~~~；
进入正文
题目描述 Description 给一个数组a1, a2 … an，找到最长的上升降子序列ab1< ab2 < .. < abk，其中b1 < b2< . .bk。
输出长度即可。
输入输出输入描述 Input Description
第一行，一个整数N。
第二行，N个整数（N < = 1000000）
输出描述 Output Description
输出K的极大值，即最长不下降子序列的长度
样例 Sample 样例输入 Sample Input
【动态规划|Codevs P3955 最长严格上升子序列(加强版)(nlogn求法)】5
9 3 6 2 7
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
n<=1000000
分析该题由于数据规模很大，使用经典的n^2算法已经不能满足时间限制。所以必须寻求一种更加迅速的算法。故有一种只能求出长度的算法。
对于第i个元素，如果比前边的大，显然直接严格上升，直接使长度+1；否则，则在前面自前向后寻找比该数大的第一个数，因为当以该数为开头的上升序列比以替换的短时，总长度保持不变，当长时，由于不断替换，那么会换出以新数的上升序列，而做法是找比其大的第一个数，那么替换以前的之后会使最后一个变小使得后面小的能够接上，从而求得了更长的序列。。。
在找第一个数时使用二分查找。从而加速了整个过程。
代码如下

program p3955; var n,i,x:longint; f:array[0..1000000] of longint; function binarysearch(l,r:longint):longint; var mid:longint; begin while l>1; if f[mid]>=x then r:=mid else l:=mid+1; end; exit(l); end; begin readln(n); f[0]:=0; for i:=1 to n do begin read(x); if x>f[f[0]] then begin inc(f[0]); f[f[0]]:=x; end else begin f[binarysearch(1,f[0])]:=x; end; end; write(f[0]); end.

评测结果运行结果
测试点#1.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#2.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#3.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#4.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#5.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#6.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#7.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#8.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#9.in 结果:AC 内存使用量: 256kB 时间使用量: 19ms
测试点#90.in 结果:AC 内存使用量: 256kB 时间使用量: 27ms
测试点#91.in 结果:AC 内存使用量: 256kB 时间使用量: 141ms
测试点#92.in 结果:AC 内存使用量: 256kB 时间使用量: 172ms
测试点#93.in 结果:AC 内存使用量: 256kB 时间使用量: 208ms
测试点#94.in 结果:AC 内存使用量: 256kB 时间使用量: 233ms
测试点#95.in 结果:AC 内存使用量: 256kB 时间使用量: 295ms
总之头疼。。。郁闷。。。