Nguồn đề bài: http://vn.spoj.com/problems/SPSEQ/
Nội dung bài viết
1. Đề bài SPSEQ spoj
W. là 1 dãy các số nguyên dương. Nó có các đặc điểm sau:
– Độ dài của dãy là 1 số lẻ: L = 2*N + 1
– N + 1 số nguyên đầu tiên của dãy tạo thành 1 dãy tăng
– N + 1 số nguyên cuối của dãy tạo thành 1 dãy giảm
– Không có 2 số nguyên nào cạnh nhau trong dãy có giá trị bằng nhau
Ví dụ: 1, 2, 3, 4, 5, 4, 3, 2, 1 là 1 dãy W. độ dài 9. Tuy nhiên, dãy 1, 2, 3, 4, 5, 4, 3, 2, 2 không là 1 dãy W.
Yêu cầu: Trong các dãy con của dãy số cho trước, tìm dãy W. có độ dài dài nhất.
Input
Dòng 1: số nguyên dương N (N <= 100000), độ dài dãy số.
Dòng 2: N số nguyên dương ai (ai <= 109).
Output
1 số nguyên dương duy nhất là độ dài dãy W. dài nhất.
Example
Input:
10
1 2 3 4 5 4 3 2 1 10
Output:
9
Input:
19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
Output:
9
2. hướng dẫn SPSEQ spoj
3. code tham khảo SPSEQ spoj
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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | const fi= ''; maxd= 100009; type data=longint; var a,kq1,kq2: array[0..maxd] of longint; l: array[0..maxd] of longint; n: longint; d: longint; 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; function min(a,b:data):data; begin if a<b then exit(a); exit(b); end; function max(a,b:data):data; begin if a>b then exit(a); exit(b); end; procedure swap(var a,b:data); var z:data; begin z:=a; a:=b; b:=z; end; procedure xuli; var i,k,dau,cuoi,res:longint; begin l[1]:=1;d:=1; kq1[1]:=1; for i:=2 to n do begin if a[i]>a[l[d]] then begin inc(d); l[d]:=i; kq1[i]:=d; 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; kq1[i]:=dau; end; end; for i:=1 to n div 2 do swap(a[i],a[n-i+1]); l[1]:=1;d:=1; kq2[1]:=1; for i:=2 to n do begin if a[i]>a[l[d]] then begin inc(d); l[d]:=i; kq2[i]:=d; 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; kq2[i]:=dau; end; end; res:=0; for i:=1 to n do res:=max(res,2*min(kq1[i],kq2[n-i+1])-1); writeln(res); end; begin nhap; xuli; end. |
