02/10/2018, 14:05
BCINCSEQ spoj PTIT – Đoạn tăng
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCINCSEQ/ 1. Đề bài BCINCSEQ spoj PTIT Cho dãy số nguyên A = (a 1 , a 2 , …, a n ). Hãy tìm một đoạn dài nhất gồm các phần tử liên ti ế p trong dãy A có thứ tự không giảm Quy ước: Đoạn chỉ gồm đúng 1 phần tử trong A cũng ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCINCSEQ/
1. Đề bài BCINCSEQ spoj PTIT
Cho dãy số nguyên A = (a1, a2, …, an). Hãy tìm một đoạn dài nhất gồm các phần tử liên tiếp trong dãy A có thứ tự không giảm
Quy ước: Đoạn chỉ gồm đúng 1 phần tử trong A cũng được coi là có thứ tự không giảm
Dữ liệu:
l Dòng 1 chứa số nguyên dương n ≤ 105
l Dòng 2 chứa n số nguyên a1, a2, …, an (“i: |ai| ≤ 109) cách nhau ít nhất một dấu cách
Kết quả:một số nguyên duy nhất là số phần tử trong đoạn tìm được
Ví dụ
| INPUT | OUTPUT |
| 1188 99 11 22 22 33 11 66 33 44 77 | 4 |
2. Hướng dẫn BCINCSEQ spoj PTIT
– Gọi F[i] là độ dài xâu con liên tiếp dài nhất kết thúc tại phần tử có giá trị là A[i].
– Nếu a[i]>=A[i-1] thì F[i]:=F[i-1]+1
– Ngược lại F[i]:=1
Kết quả bài toán là F[n].
Khởi tạo F[0]=0; A[0]=dương vô cực.
3. code tham khảo BCINCSEQ spoj PTIT
CONST FI=';
nmax=100000;
type data=longint;
var
f:text;
a:array[0..nmax+1] of data;
n,i,j,max:data;
C:array[0..nmax+1] of data;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
a[0]:=high(data);
close(f);
end;
begin
docfile;
max:=0;
for i:=1 to n do
if a[i-1]<=a[i] then
C[i]:=C[i-1]+1
else
C[i]:=1;
for i:=1 to n do
if c[i]>max then
max:=c[i];
writeln(max);
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 | CONST FI='; nmax=100000; type data=longint; var f:text; a:array[0..nmax+1] of data; n,i,j,max:data; C:array[0..nmax+1] of data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do read(f,a[i]); a[0]:=high(data); close(f); end; begin docfile; max:=0; for i:=1 to n do if a[i-1]<=a[i] then C[i]:=C[i-1]+1 else C[i]:=1; for i:=1 to n do if c[i]>max then max:=c[i]; writeln(max); end. |
