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 |
01 02 03 04 05 06 07 08 09 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 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 . |