编程介的小学生 2019-12-31 22:41 采纳率: 20.5%
浏览 101

Wooden Sticks

Problem Description
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

Sample Output
2
1
3

  • 写回答

0条回答 默认 最新

    报告相同问题？

    • 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
    • WoodenSticks
      2014-01-11 19:54
      Wooden Stickes 问题 现有n 根木棒，已知它们的长度和重量。要用一部木工机一根根加工，该机器在加工过程中需要一定的准备时间，是用于清洗机器在，调整工具和模板。 木工机需要的准备时间如下： （1）第1根需要1...
    • 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
    • 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 ...
    • 《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（贪心）
      2022-04-04 08:55
      Ustinian.'的博客 题目描述 现有n根木棒，已知它们的长度和重量。要用一部木工机一根一根地加工这些木棒。该机器在加工过程中需要一定的准备时间，是用于清洗机器，调整工具和模版的。 木工机需要的准备时间如下： ...
    • HDU Wooden Sticks
      2019-10-06 08:19
      anvt77205的博客 Wooden Sticks http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=1&sectionid=3&problemid=16 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K ...
    • Wooden Sticks-贪心
      2020-05-28 21:27
      千千开心啊的博客 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 ...
    • Wooden Sticks POJ - 1065
      2017-08-26 14:34
      sunyutian1998的博客 根据每根棍子有长与重 首先想到了坐标轴上点的横纵坐标 这样该问题就可以抽象为 类似于拦截导弹问题的最长严格升或降子序列问题   这里l为x w为y 先将所有坐标平面上的点按横坐标从小到大排序 相等则按纵坐标...
    • 没有解决我的问题, 去提问

    悬赏问题

    • ¥60 版本过低apk如何修改可以兼容新的安卓系统
    • ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
    • ¥50 有数据，怎么建立模型求影响全要素生产率的因素
    • ¥50 有数据，怎么用matlab求全要素生产率
    • ¥15 TI的insta-spin例程
    • ¥15 完成下列问题完成下列问题
    • ¥15 C#算法问题, 不知道怎么处理这个数据的转换
    • ¥15 YoloV5 第三方库的版本对照问题
    • ¥15 请完成下列相关问题！
    • ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像，如何解决？