WOODEN STICK - mã: MSTICK - SPOJ

Link: http://vn.spoj.com/problems/MSTICK/

Có n đoạn gỗ. Để xử lý chúng cần thời gian để chuẩn bị : 

(a) Thời gian chuẩn bị cho đoạn gỗ đầu tiên là 1 phút. 

(b) Sau khi xử lý xong đoạn gỗ có chiều dài l và trọng lượng w , không mất 

thời gian xử lý nếu đoạn gỗ tiếp theo có độ dài l' và trọng lượng w' thỏa

l ≤ l' and  w ≤ w'. Ngược lại mất 1 phút để chuẩn bị.

Tìm thời gian chuẩn bị ít nhất cho n đoạn gỗ. Ví dụ có 5 đoạn ( 9 , 4 ) , 

( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , và ( 4 , 1 ) , thì thời gian ít nhất là 2

 vì có thể  xử lý theo thứ tự như sau ( 4 , 1 ) , 

( 5 , 3 ) , ( 9 , 4 ) ,

( 1 , 2 ) , ( 2 , 5 ) .

Input

Dòng đầu là số lượng test, T. Mỗi test gồm 2 dòng : dòng đầu là số n , 1 <= n <= 5000 , 

và dòng thứ hai gồm 2n số nguyên dương l1 , w1 , l2 , w2 ,..., ln , wn ,

<= 10000 , li và wi là độ dài và trọng lượng của đoạ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 ít nhất trên từng dòng.

SAMPLE OUTPUT

2

1

3

===================================

Bài này trước tiên ta Sort tăng các khối gỗ theo L, giống như bài NESTED DOLLS, ta sử dụng Quicksort lồng, để khi giá trị Lbằng nhau, ta lại cho W tăng dần, Quicksort lồng được mô tả như sau:

procedure Sort(Q,H: integer);
var t,i,j,k,kk: integer;
begin
    i:=Q; j:=H; k:=L[(Q+h) div 2]; kk:=W[(q+h) div 2];
    repeat
      while (L[i]<k) or ((L[i]=k) and (W[i]<kk)) do inc(i);
      while (L[j]>k) or ((L[j]=k) and (W[j]>kk)) do dec(j);
      if i<=j then
        begin
          t:=L[i]; L[i]:=L[j]; L[j]:=t;
          t:=W[i]; W[i]:=W[j]; W[j]:=t;
          inc(i); dec(j);
        end;
    until i>j;
    if q<j then Sort(q,j);
    if i<h then Sort(i,h);
end;

Tiếp theo ta tìm dãy con giảm cực đại với mảng W, độ dài dãy con giảm chính là đáp án bài toán......hết !!!