Đoạn gỗ

Tiêu đề: Đoạn gỗ Tue 27 Jul 2010, 13:24

Có n đoạn gỗ. Để xử lý chúng cần thời gian để chuẩn bị :

(a) Thời gian chuẩn bị cho đoạn gỗ đầu tiên là 1 phút.
(b) Sau khi xử lý xong đoạn gỗ có chiều dài l và trọng lượng w , không mất
thời gian xử lý nếu đoạn gỗ tiếp theo có độ dài l' và trọng lượng w' thỏa
l ≤ l' and w ≤ w'. Ngược lại mất 1 phút để chuẩn bị.

Tìm thời gian chuẩn bị ít nhất cho n đoạn gỗ. Ví dụ có 5 đoạn ( 9 , 4 ) ,
( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , và ( 4 , 1 ) , thì thời gian ít nhất là 2
vì có thể xử lý theo thứ tự như sau ( 4 , 1 ) ,
( 5 , 3 ) , ( 9 , 4 ) ,
( 1 , 2 ) , ( 2 , 5 ) .

Input

Dòng đầu là số lượng test, T. Mỗi test gồm 2 dòng : dòng đầu là số n , 1 <= n <= 5000 ,
và dòng thứ hai gồm 2n số nguyên dương l1 , w1 , l2 , w2 ,..., ln , wn ,
<= 10000 , li và wi là độ dài và trọng lượng của đoạn gỗ thứ i.

SAMPLE INPUT
3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

Output

Ghi ra thời gian ít nhất trên từng dòng.
SAMPLE OUTPUT
2
1
3
Hướng dẫn: Bài này sử dụng tìm kiếm nhị phân!

Tiêu đề: Re: Đoạn gỗ Wed 28 Jul 2010, 11:02

Làm giống bài đoạn nguyên thôi

Tiêu đề: Re: Đoạn gỗ Wed 28 Jul 2010, 15:46

Bài đoạn nguyên mình đã làm và AC rồi.

Code:: Var N,M:longint;
A,B,F,L:Array[0..100001] of longint;

Procedure Input;
Var i:longint;
Begin
Readln(N);
For i:=1 to N do Readln(A[i],B[i]);
End;

Procedure Init;
Begin
A[0]:=Low(longint);
A[N+1]:=High(longint);
M:=1;
L[N+1]:=1;
F[1]:=N+1;
End;

Procedure Sort(L,R:longint);
Var i,j,Tam,Tam1,Key,Key1:longint;
Begin
If L>=R then Exit;
i:=L;
j:=R;
Key:=B[(L+R) div 2];
Key1:=A[(L+R) div 2];
Repeat
While (B[i]>Key) or ((B[i]=Key) and (A[i]<Key1)) do Inc(i);
While (B[j]<Key) or ((B[j]=Key) and (A[j]>Key1)) do Dec(j);
If i<=j then
Begin
Tam:=B[i];
B[i]:=B[j];
B[j]:=Tam;
Tam1:=A[i];
A[i]:=A[j];
A[j]:=Tam1;
Inc(i);
Dec(j);
End;
Until i>j;
Sort(L,j);
Sort(i,R);
End;

Function Find(i:longint):longint;
Var Dau,Cuoi,Giua,j:longint;
Begin
Dau:=1;
Cuoi:=M+1;
Repeat
Giua:=(Dau+Cuoi) div 2;
j:=F[giua];
If A[j]>=A[i] then Dau:=Giua
Else Cuoi:=Giua;
Until Dau+1=Cuoi;
Find:=F[Dau];
End;

Procedure Xuli;
Var i,j,k:longint;
Begin
For i:=N downto 0 do
Begin
j:=Find(i);
K:=L[j]+1;
If K>M then
Begin
M:=K;
F[K]:=i;
End
Else
If A[F[K]]<A[i] then F[K]:=i;
L[i]:=K;

End;
End;

Procedure Output;
Begin
Writeln(M-2);
End;

BEGIN
Input;
Init;
Sort(1,N);
Xuli;
Output;
END.

Tiêu đề: Re: Đoạn gỗ Wed 28 Jul 2010, 15:48

Còn bài trên thì thử các test thấy đúng nhưng nộp vẫn bị wa.

Code:: Const MaxN=5001;
Var T,h:longint;
N,M:longint;
A,B,F,L:Array[0..MaxN] of longint;

Procedure Input;
Var i:longint;
Begin
Readln(N);
For i:=1 to N do Read(A[i],B[i]);
End;

Procedure Init;
Begin
B[0]:=Low(longint);
B[N+1]:=High(longint);
M:=1;
L[N+1]:=1;
F[1]:=N+1;
End;

Procedure Sort(L,R:longint);
Var i,j,Key,Key1,Tam,Tam1:longint;
Begin
If L>=R then Exit;
i:=L;
j:=R;
Key:=A[(L+R) div 2];
Key1:=B[(L+R) div 2];
Repeat
While (A[i]>Key) or ((A[i]=Key) and (B[i]<Key1)) do Inc(i);
While (A[j]<Key) or ((A[j]=Key) and (B[j]>Key1)) do Dec(j);
If i<=j then
Begin
Tam:=A[i];
A[i]:=A[j];
A[j]:=Tam;
Tam1:=B[i];
B[i]:=B[j];
B[j]:=Tam1;
Inc(i);
Dec(j);
End;
Until i>j;
Sort(L,j);
Sort(i,R);
End;

Function Find(i:longint):longint;
Var Dau,Cuoi,Giua,j:longint;
Begin
Dau:=1;
Cuoi:=M+1;
Repeat
Giua:=(Dau+Cuoi) div 2;
j:=F[giua];
If B[j]>B[i] then Dau:=Giua
Else Cuoi:=Giua;
Until Dau+1=Cuoi;
Find:=F[Dau];
End;

Procedure Xuli;
Var i,j,k:longint;
Begin
For i:=N downto 0 do
Begin
j:=Find(i);
K:=L[j]+1;
If K>M then
Begin
M:=K;
F[K]:=i;
End
Else
If B[F[K]]<B[i] then F[K]:=i;
L[i]:=K;

End;
End;

Procedure Output;
Begin
If h<T then Writeln(M-2)
Else Write(M-2);
End;

BEGIN
Readln(T);
For h:=1 to T do
Begin
Input;
Init;
Sort(1,N);
Xuli;
Output;
End;
END.

Tiêu đề: Re: Đoạn gỗ Thu 29 Jul 2010, 18:09

Cái này còn tùy anh à. Một tỉ lệ nhỏ là đáp số bị sai. Nhưng nhỏ và rất rất nhỏ thôi. Như ở chỗ em nè, thầy ra đề, em làm đúng cuối cùng đáp số sai. laughing

Tiêu đề: Re: Đoạn gỗ Thu 29 Jul 2010, 22:43

Anh chẳng thấy sai chỗ nào cả!

Tiêu đề: Re: Đoạn gỗ Fri 30 Jul 2010, 11:55

Ko, ý em là đáp án của đề á.

» Các đoạn nguyên
» Nhà tiên tri Vanga dự đoán Chiến tranh Thế giới Thứ 3 sẽ nổ ra vào năm 2010