A30010.Wooden Sticks

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Lialosiu要制作木棍,给n根作为原料的木棍的长度和重量。根据要求求出制作木棍的最短时间。
首先我们知道制作第一个木棍需要1分钟,若是接着要制作的木棍的重量和长度都不少于当前的木棍,那么就不需要建立的时间,若是没有,则再需要建立时间,也就是1分钟。
举个例子,如果你有五个原料木棍,他们的长度和重量分别是(4,9), (5,2), (2,1), (3,5), 和 (1,4), 那么第一分钟你要建立一根木棍作为起始参照,比如(1,4)接下来(3,5)和(4,9)都可以不花费时间,然后用第二分钟选取(2,1

输入格式

首先,输入一个正整数T ,代表有T组数据。
接下来,第二行你要输入正整数n(1 <=n <=5000)代表的你的原料木棍个数。
第三行你要输入2*n 个 正整数l1, w1, l2, w2, ..., ln, wn,每一个数字都不超过10000 。 li代表第i根木棍的长度,wi代表第i根木棍的重量。

输出格式

输出一个整数,代表最少需要的时间t。

输入输出样例

  • 输入#1

    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
    

    输出#1

    2
    1
    3
    
首页