Bài giải:
Input : Dữ liệu vào từ file SUPERNUM.INP :
• Dòng đầu là số T (1 ≤ T ≤ 10) là số bộ test bạn phải giải quyết.
• T nhóm dòng sau,mỗi nhóm gồm 2 dòng:
• Dòng đầu là số N.
• Dòng thứ 2 chứa N số nguyên từ 1 tới N.
Output : Dữ liệu ra ghi lên file SUPERNUM.OUT gồm T dòng,mỗi dòng ghi các số đặc biệt của bộ test tương ứng theo thứ tự tăng dần.
SUPERNUM.INP |
SUPERNUM.OUT |
2
7
1 2 3 7 4 5 6
5
1 4 3 2 5 |
6
1 2 3 4 5 6
5
1 2 3 4 5 |
Lưu ý:Bài tóan này có thể sử dụng Free Pascal để giải quyết .
Thuật giải : Gọi
K,F[I],G[I} lần lượt là độ dài của dãy tăng dài nhất,dãy tăng dài nhất
kết thúc tại A[I],dãy tăng dài nhất bắt đầu từ A[I].Như vậy A[I] là một
số đặc biệt khi và chỉ khi F[I]+G[I]=K+1.Do đó bài tóan đã được đưa về
dạng quy họach động cơ bản thường thấy là tìm dãy con tăng dài
nhất.Cách giải thông thường với lọai bài này có độ phức tạp N 2 ,dĩ
nhiên không thể áp dụng ở đây do N quá lớn (≤ 10 5 ).Vì vậy ta cần phải
hướng tới một thuật giải khác có độ phức tạp nhỏ hơn,ở đây xin giới
thiệu với bạn đọc phương pháp tìm dãy con tăng dài nhất với độ phức tạp
NlogN,bộ nhớ tỷ lệ với N:
• Gọi F[I] là độ
dài dãy tăng dài nhất kết thúc tại I,S[I] là giá trị nhỏ nhất trong số
các phần tử kết thúc của các dãy tăng có độ dài I.
• Tại mỗi thời điểm I:lưu giữ K là độ dài của dãy con tăng dài nhất tới thới điểm đó.Tìm J max sao cho S[J]<A[I] khi đó :
• F[I]:=J+1.
• Nếu S[F[I]]>A[I] thì S[F[I]]:=A[I].
• Nếu F[I]>K thì K:=F[I].
•
Với cách tính như trên dễ thấy tại mỗi thời điểm dãy S là dãy tăng :
S[1]<S[2]<….<S[I] (có thể chứng minh bằng quy nạp ).Điều này
có nghĩa là mỗi lần tính J ta chỉ phải tốn thời gian tỷ lệ với logN,do
đó độ phức tạp của thuật tóan chỉ là NlogN.
Source Code : Sau đây là chương trình được cài đặt theo tư tưởng ở trên (chạy trên Free Pascal ):
{ ------------------------------------------------------------ }
Const input='supernum.inp';
output='supernum.out';
maxn=10000;
Var f,g:text;
n,test,t,l,kmax:longint;
a,incs,decs,s:array[1..maxn] of longint;
Function Find(x:longint):longint;
Var tmax,left,right,mid:longint;
Begin
left:=1;right:=kmax;tmax:=0;
Repeat
mid:=(left+right) shr 1;
If s[mid]>a[x] then right:=mid-1 else
If s[mid]<a[x] then
Begin
left:=mid+1;
tmax:=mid;
End;
Until left>right;
Find:=tmax;
End;
Procedure SolveProblem;
Var i,t,longest,dem:longint;
Begin
incs[1]:=1;s[1]:=a[1];kmax:=1;a[1]:=-a[1];
For i:=2 to n do
Begin
t:=Find(i);
incs[i]:=t+1;
If incs[i]>kmax then
Begin
kmax:=incs[i];
s[kmax]:=a[i];
End
Else If s[incs[i]]>a[i] then s[incs[i]]:=a[i];
a[i]:=-a[i];
End;
decs[n]:=1;s[1]:=a[n];kmax:=1;
longest:=decs[n]+incs[n];dem:=0;
For i:=n-1 downto 1 do
Begin
t:=Find(i);
decs[i]:=t+1;
If decs[i]>kmax then
Begin
kmax:=decs[i];
s[kmax]:=a[i];
End
Else If s[decs[i]]>a[i] then s[decs[i]]:=a[i];
If longest<decs[i]+incs[i] then longest:=decs[i]+incs[i];
End;
Fillchar(s,sizeof(s),0);
For i:=1 to n do
If (incs[i]+decs[i])=longest then
Begin
Inc(dem);
s[-a[i]]:=1;
End;
Writeln(g,dem);
For i:=1 to n do
If s[i]=1 then Write(g,i,' ');
Writeln(g);
End;
Begin
Assign(f,input);Reset(f);
Assign(g,output);Rewrite(g);
Readln(f,test);
For t:=1 to test do
Begin
Readln(f,n);
For l:=1 to n do
Read(f,a[l]);
SolveProblem;
End;
Close(f);Close(g);
End.
3Cdotcom “Web Hosting - Bền vững cho Thương hiệu" www.hosting.net.vn