Nguồn đề bài http://vn.spoj.com/problems/LIS/ Đề bài LIS Spoj Tìm dãy con tăng dài nhất, số lượng phần tử tối đa 30000. In ra số lương lớn nhất có thể Input: 5 2 1 4 3 5 Output: 3 Link nộp bài: http://vn.spoj.com/problems/LIS/ Code Lis spoj Pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | const fi= ''; fo= ''; maxd= 30001; var a: array[0..maxd] of longint; l: array[0..maxd] of integer; n: longint; d: longint; procedure mofile; var i,j:integer; begin assign(input,fi);reset(input); assign(output,fo);rewrite(output); end; procedure dongfile; begin close(input);close(output); end; procedure nhap; var i:longint; f:text; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do read(f,a[i]); close(f); end; procedure xuli; var i,k,dau,cuoi:longint; begin l[1]:=1;d:=1; for i:=2 to n do begin if a[i]>a[l[d]] then begin inc(d); l[d]:=i; end else begin dau:=1; cuoi:=d; while dau<cuoi do begin k:=(dau+cuoi) div 2; if a[l[k]]<a[i] then dau:=k+1 else cuoi:=k; end; l[dau]:=i; end; end; end; procedure xuat; begin write(d); end; begin nhap; xuli; xuat; end. |
