编程介的小学生 2017-02-19 07:30 采纳率: 20.5%
浏览 869
已采纳

Wooden Sticks

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l<=l' and w<=w'. Otherwise, it will need 1 minute for setup.

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains n 2 positive integers l1, w1, l2, w2, ..., ln, wn, each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

Output

The output should contain the minimum setup time in minutes, one per line.

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 for the Sample Input

2
1
3

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-02-23 15:40
    关注

    http://blog.csdn.net/lishuhuakai/article/details/8117251

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题？

  • Wooden Sticks
    2017-02-19 07:30
    回答 2 已采纳 http://blog.csdn.net/lishuhuakai/article/details/8117251
  • C/C++杭电1501题Wooden sticks 求挑错 算法
    2016-03-19 05:41
    回答 1 已采纳 http://blog.csdn.net/lishuhuakai/article/details/8117251
  • Wooden_Sticks问题一直wrong，希望指出我程序错误的地方 c语言
    2021-03-08 23:09
    回答 2 已采纳 我找不出来哪里错了. c++做法, 用了一个sort排序(懒懒排序), 其他的用C语言也可以实现.希望这个代码能帮到你.  #include <cstdio> #include &l
  • 贪心算法 WOODEN STICKS 实例代码
    2020-09-05 07:36
    贪心算法 WOODEN STICKS 实例代码，需要的朋友可以参考一下
  • Sticks
    2017-09-13 00:47
    回答 1 已采纳 http://blog.csdn.net/qq_32426313/article/details/52083559
  • Sticks Problem
    2016-12-16 08:39
    回答 1 已采纳 http://blog.csdn.net/guard_mine/article/details/45748253
  • Magic Sticks
    2017-12-10 13:32
    回答 1 已采纳 https://blog.csdn.net/Baiyi_destroyer/article/details/81271213
  • Wooden Sticks
    2021-10-24 14:20
    鬼怪、的博客 There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called ...
  • Pick-up Sticks
    2017-03-24 11:10
    回答 2 已采纳 http://blog.csdn.net/itaskyou/article/details/51356970
  • Hiiragi's Sticks
    2017-06-05 04:50
    回答 2 已采纳 http://blog.csdn.net/m0_37134257/article/details/70879631
  • Pick-up sticks
    2017-01-03 05:30
    回答 1 已采纳 http://blog.csdn.net/Enjoying_Science/article/details/47768561
  • WoodenSticks
    2014-01-11 19:54
    Wooden Stickes 问题 现有n 根木棒，已知它们的长度和重量。要用一部木工机一根根加工，该机器在加工过程中需要一定的准备时间，是用于清洗机器在，调整工具和模板。 木工机需要的准备时间如下： （1）第1根需要1...
  • 《Wooden Sticks》
    2020-01-17 10:09
    算法小学习家的博客 There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, call...
  • wooden sticks
    2019-08-14 06:51
    weixin_30788731的博客 这道题的思路是对木棍的长度排序，如果相同再按重量排序，从小到大。 这题不知道为什么，我用qsort排序是wrong answer ..一用sort排序时，就AC啦。。 View Code 1 #include<stdio.h>...alg...
  • 没有解决我的问题, 去提问

悬赏问题

  • ¥20 有关区间dp的问题求解
  • ¥15 多电路系统共用电源的串扰问题
  • ¥15 slam rangenet++配置
  • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
  • ¥15 对于相关问题的求解与代码
  • ¥15 ubuntu子系统密码忘记
  • ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
  • ¥15 保护模式-系统加载-段寄存器
  • ¥15 电脑桌面设定一个区域禁止鼠标操作
  • ¥15 求NPF226060磁芯的详细资料