Bài toán. Cho dãy số nguyên A = a1, a2, …, an (1≤n≤5000, -10000≤ai≤10000). Một dãy con của A là một cách chọn ra trong A một số phần tử và giữ nguyên thứ tự.
Yêu cầu: Tìm dãy con đơn điệu tăng của dãy A có độ dài lớn nhất.
Dữ liệu vào: Cho từ file văn bản INCSEQ.INP
- Dòng đầu ghi số n
- Dòng thứ hai ghi n số a1, a2, …, an cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản INCSEQ.OUT
- Dòng đầu ghi độ dài của dãy con tìm được
- Các dòng tiếp theo, mỗi dòng ghi hai số tương ứng là chỉ số và giá trị của phần tử được chọn trong dãy A theo thứ tự từ đầu đến cuối.
Ví dụ:
|
INCSEQ.INP |
INCSEQ.OUT |
|
10 3 9 4 8 6 2 1 7 10 5 |
5 1 3 3 4 5 6 8 7 9 10 |
Const fin ='INCSEQ.INP';
fout='INCSEQ.OUT';
Var L,Truoc,a:array[1..5001] of integer;
n,m,i,k:integer;
f:text;
Begin
Assign(f,fin);
Reset(f);
Readln(f,n);
For i:=1 to n do Read(f,a[i]);
Close(f);
L[n+1]:=0;
For k:=n downto 1 do
Begin
m:=n+1;
For i:=k+1 to n do
If (a[k]<a[i]) and (L[i]>L[m]) then m:=i;
L[k]:=L[m]+1;
Truoc[k]:=m;
End;
m:=1;
For i:=2 to n do
If L[i]>L[m] then m:=i;
Assign(f,fout);
ReWrite(f);
Writeln(f,L[m]);
Repeat
Writeln(f,m,' ',a[m]);
m:=Truoc[m];
Until m>n;
Close(f);
End.