Dãy con đơn điệu tăng dài nhất trong Pascal

48
Lập trình Pascal

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.