Nguồn đề bài http://vn.spoj.com/problems/LIS/
Nội dung bài viết
Đề 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. |
Bài viết liên quan
- BLGEN spoj – Chuỗi gen đặc trưng
- MTHCN spoj – Hình chữ nhật kì lạ
- SPSEQ spoj – Sequences
- MAXARR1 spoj – Help Conan 12 !
- MTTRAVEL spoj THPTCBT – Du lịch vòng quanh thế giới
- lời giải LATGACH spoj – Lát gạch
- BONUS spoj – VOI 2011 Phần thưởng
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- TNHWIFI spoj – Cafe wifi
- MPILOT spoj – Pilots
Có thuật nào chạy đc tới 10^5 không đại ca ?
ko có :/
không có gì em?
anh oi cho em hoi vi sao mid = (d+c+1) div 2 ,chu khong phai la (d+c) div 2