MSTICK - Wooden Sticks

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/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

Được gửi lên bởi:psetter
Ngày:2009-02-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Taejon 2002

hide comments
2021-05-27 18:02:05
Tham khảo: https://vnspoj.github.io/problems/MSTICK
2019-09-17 14:54:30
bai nay luong cuc dai co ban
duonght_pro_xinhgainhathemattroi-:)
2017-05-17 11:10:27
Hài thật. Nhiều test mà sử dụng write :)
2016-04-17 03:00:45
bài này y rang bài búp bê
2016-03-20 04:39:41
Bài này test case 1 phải ra 1 chứ!
2010-12-23 01:29:39 xuanson94
bai nay so test cho bao nhieu the ha ong gioi????????moi nguoi noi cho toi bit voi

2009-09-02 10:02:25 loc_konoko
Bai nay tuong tu bup be^^
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.