02/10/2018, 13:57
SPSEQ spoj – Sequences
Nguồn đề bài: http://vn.spoj.com/problems/SPSEQ/ 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 ...
Nguồn đề bài: http://vn.spoj.com/problems/SPSEQ/
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
+Mảng QHĐ:
– T[i] độ dãy con tăng dài nhất từ 1 -> i nhận a[i] làm phần tử cuối cùng
– S[i] độ dãy con tăng dài nhất từ n -> i nhận a[i] làm phần tử cuối cùng
– 2 mảng trên tính bằng bài LIS
+Kết quả : res = max{2 * min(F[i], S[i]) – 1} với i = 1 -> n
3. code tham khảo SPSEQ spoj
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.
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. |
