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

0

2个回答

0
0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
POJ 1065 Wooden Sticks 解题报告-用动态规划方法解决(LIS变式)
POJ 1065 Wooden Sticks 解题报告-用动态规划方法解决(LIS变式)DescriptionThere 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 mach
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: nn(a) The setup time for the first wooden stick is 1 minute. n(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. nnYou 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). nnInput nnThe 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. nnOutput nnThe output should contain the minimum setup time in minutes, one per line. nnnSample Input nn3 n5 n4 9 5 2 2 1 3 5 1 4 n3 n2 2 1 1 2 2 n3 n1 3 2 2 3 1nnnOutput for the Sample Inputnn2 n1 n3
Wooden Sticks(区间覆盖)
Wooden Sticks nTime Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u nSubmitStatus nDescription nThere is a pile of n wooden sticks. The length and weight of each stick are known
【HPUoj】Wooden Sticks(贪心)
题目链接:点击打开链接rnrnrnrn问题 F: Wooden Sticksrn时间限制: 1 Sec 内存限制:rn 128 MBrnrn提交: 1  解决:rn 1  状态rnrn题目描述rnrnLialosiu要制作木棍,给n根作为原料的木棍的长度和重量。根据要求求出制作木棍的最短时间。rn首先我们知道制作第一个木棍需要1分钟,若是接着要制作的木棍的重量和长度都不少于当前的木棍,那么就不需要
贪心算法——Wooden Sticks
DescriptionnnThere 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 som
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 ...
Sticks (dfs经典剪枝)
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had orig
poj(1011)——Sticks(经典的dfs+剪枝)
题目的大致意思是:rn现在有n根木棍,然后需要把它们拼成同样长度的木棍,问满足这个条件的最短的长度是多少?rn想法嘛:那肯定是dfs把长度搜一遍就好,但问题的关键是这里会超时。那么就要用到剪枝的原理了。rn以下部分是来自于pku的gw老师说哒rn1)不要在同一个位置多次尝试相同长度的木棒(在某一次拼接时选择长度为s的木棒导致拼接失败,则在同一位置尝试下一根木棒时,要跳过所有长度为s的木棒)rn2)
POJ 1011 Sticks【深搜+剪枝】
SticksnnTime Limit: 1000MS Memory Limit: 10000K nTotal Submissions: 152276 Accepted: 36300nnDescriptionnnGeorge took sticks of the same length and cut them randomly until all parts became a...
hdu 5914 Triangle【斐波那契数列】
TrianglernrnTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)rnTotal Submission(s): 388    Accepted Submission(s): 263rnrnProblem DescriptionrnMr. Frog has n sticks,
桌面便签软件Sticks
国外的一款免安装版的桌面便签软件,支持定时提醒,方便大家管理纷繁复杂的工作事物
ZOJ 1025 Wooden Sticks 【思维 + 最长下降子序列 + Dilworth定理】
传送门 n// 题意: 有n个木头, 每个木头有一个长度和重量. 每次一根木头准备需要1分钟, 如果下一根木头的(l’, w’) l’ >= l, w’ >= w, 那么就不用多余准备时间, 否则准备时间加1, 问处理掉这些木头最少需要多少分钟.思路: 有一个很明显的二维偏序关系在里面, 那么假设我们只看一维, 那么就是问最少可以划分多少组最长不下降子序列, 那么由这个Dilworth定理我们可以转
【POJ-2452】Sticks Problem【二分右端点+线段树】
题意:nn      给定一个数组序列,找到一段区间 [ i , j ],使得区间a[i] &amp;lt; a[k] &amp;lt; a[j],( k 是 [ i , j ] 中任意一个数),此处注意 a[i] 是区间唯一最小值,a[j] 是区间唯一最大值。nn      求 j-i 最大值。(n &amp;lt;= 50000)nn nn思路:nn      确定左端点,然后找到一个最长区间,使得该区间的最小值为左...
HDU:1051 Wooden Sticks(贪心+动态规划DP||LIS?)
Wooden SticksrnTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)rnTotal Submission(s): 18567    Accepted Submission(s): 7574rnrnrnrnProblem DescriptionrnrnThere is a
POJ-1065 Wooden Sticks 动态规划之求下降子序列的个数。
有N根木棍等待处理。机器在处理第一根木棍时需要准备1分钟,此后遇到长宽都不大于前一根木棍的木棍就不需要时间准备,反之则需要1分钟重新准备。比如木棍按照(3,3)、(1,3)、(1,4)、(2,3)的顺序进入,共需要准备3分钟 nInput n第一行是T,表示测试数据个数。测试数据的第一行是N(1 &amp;lt;= N &amp;lt;= 5000)此后一行是 l1 , w1 , l2 , w2 ,…, ln ,...
C/C++杭电1501题Wooden sticks 求挑错
DescriptionnThere 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:nn(a) The setup time for the first wooden stick is 1 minute.n(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.nnYou 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).n nnInputnThe 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.n nnOutputnThe output should contain the minimum setup time in minutes, one per line.n nnSample Inputnn3 n5 n4 9 5 2 2 1 3 5 1 4 n3 n2 2 1 1 2 2 n3 n1 3 2 2 3 1 nn nnSample Outputnn2n1n3 nnnnnnnnnn#includen#includennusing namespace std;nnstruct sticknn int len;n int wei;n bool judge;ns[10009];nnint cmp(stick a,stick b)nn if(a.len!=b.len)n return a.len>T;n while(T--)n n cin>>n;n for(i=0;i>s[i].len>>s[i].wei;n s[i].judge=true;n n sort(s,s+n,cmp);n time=0;n int flag_len=s[0].len,flag_wei=s[0].wei,num;n for(i=0;i=flag_len&&s[j].wei>=flag_wei)n n s[j].judge=false;n num++;n n n if(num)time++;n for(j=i+1;j
Sticks题解
DescriptionGeorge took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks h
poj1065 Wooden Sticks(没有交集元素的lis的条数)
题意:给你n个棍子,棍子有两个属性l和w,开启机器加工这些棍子,如果满足l1<=l2且w1<=w2,加工完棍子1之后便可以加工棍子2,否则要再次启动机器,问最少要启动几次? n题意等价于:给出若干个偏序,求出这样一个集合的大小,该集合中任意两个偏序都不可比较。分析:如果将棍子按照其中一个属性升序(属性值相同就按另一属性值升序),那么就是求另一个属性的lis链最少条数,要求各条lis链之间不包含相同下
POJ-1065 Wooden Sticks,排序+最长单减子序列!
Wooden Sticksnnnn   题意:有一台机器处理木材,最开始需要一分钟准备,如果后面处理的木材比前面处理的木材更长更重,则不需要准备时间,否则需要分钟准备时间。n  思路:按长度排序然后求重量的一个最长单减子序列就好了。struct noden{n int x,y;n}a[N];nint b[N];nint cmp(node a,node b)n{n if(a.x
挑战练习题2.3动态规划 poj1065 Wooden Sticks 最长递减子序列
题目链接:http://poj.org/problem?id=1065题意:C小加有一些木棒,它们的长度和质量都已经知道,需要一个机器处理这些木棒,机器开启的时候需要耗费一个单位的时间,如果第i+1个木棒的重量和长度都大于等于第i个处理的木棒,那么将不会耗费时间,否则需要消耗一个单位的时间。因为急着去约会,C小加想在最短的时间内把木棒处理完,你能告诉他应该怎样做吗?题解:最小值其实等于按l递增排序后
HDU 1051 Wooden Sticks (贪心 + 读不懂题目系列)
思路:按照length排序,如果length一样,按照weight排序,然后暴力枚举。 n坑点:题目中的right after 代表着每个树枝最多使之后的一个树枝的花费变成0; n了解了这一点就没有什么难的了。。AC代码:#include <iostream>n#include <iomanip>n#include <cmath>n#include <cstdio>n#include <algori
poj 1065 Wooden Sticks (求最长非降子序列的个数)
点击打开链接rn题意:n根木材长l_i重w_i,前一根木材大于后一根的话要浪费一分钟准备机器,求最省方案?rn思路:首先会想到求得是最长非降子序列的个数,那么如何实现,似乎没有足够巧妙地方案,细心观察数据就能得出这样的结论:先对l按从小到大的顺序 排序,然后得到的序列中w的最长递减子序列的长度就是答案。rn #includen#includen#includen#includen#inclu
POJ 1065 Wooden Sticks 最长不上升子集 偏序定理
题目链接: POJ—1065 Wooden Sticks n题目大意: 一堆木头拥有l,w两个值,必须按照l<=l’&&w<=w’的顺序才能排成一队,求多少组。 n题目分析: l为第一关键字,w为第二关键字从小到大排列。然后求w中的最长不上升子集。PS: n1、里面那个vector用的不好。。。应该直接数组,然后把vec[0] = INF就比较方便了,不得已只能把r设成-1,写的好丑。。。 n2、最
POJ - 1065 Wooden Sticks 贪心+最长上升子序列
题目:http://poj.org/problem?id=1065nn大意:nn有N根木棍等待处理。机器在处理第一根木棍时需要准备1分钟,此后遇到长宽都不大于前一根木棍的木棍就不需要时间准备,反之则需要1分钟重新准备。比如木棍按照(3,3)、(1,3)、(1,4)、(2,3)的顺序进入,共需要准备3分钟nnnn思路: 看数据,n&lt;=5000, 长重都&lt;=10000,是否需要重新准备...
POJ1127 Jack Straws(判断线段相交+Floyd-Warshall求传递闭包)
题目链接nnJack StrawsnnDescriptionnnIn the game of Jack Straws, a number of plastic or wooden "straws" are dumped on the table and players try to remove them one-by-one without disturbing the other straws...
Sticks Problem--(单调队列)
Xuanxuan has n sticks of different length. One day, she puts all her sticks in a line, represented by S1, S2, S3, ...Sn. After measuring the length of each stick Sk (1 <= k <= n), she finds that for some sticks Si and Sj (1<= i < j <= n), each stick placed
Sticks (经典搜索加剪枝)
SticksnnTime Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)nnTotal Submission(s) : 30   Accepted Submission(s) : 7nnFont: Times New Roman | Verdana | GeorgiannFont Size: ←...
回溯法Square
SquarernDescriptionrnGiven a set ofsticks of various lengths, is it possible to join them end-to-end to form asquare?rnInputrnThe first line ofinput contains N, the number of test cases. Each test cas
POJ 1011 Sticks(搜索问题)
题目链接 nhttp://bailian.openjudge.cn/practice/1011/nn思路一(TLE): n输入数据时,计算出需要枚举的原始棍子长度的上界下界,然后枚举。对每一个stick,将他归到某一组棍子中(如果当前枚举的原始棍子长度为i,一组棍子的总和就应该恰好是i),然后搜索。nn#include &amp;lt;iostream&amp;gt;n#include &amp;lt;algorithm...
经典剪枝算法的例题——Sticks详细注释版
这题听说是道十分经典的剪枝算的题目,不要问我剪枝是什么,我也不知道,反正我只知道用到了深度搜索我参考了好多资料才悟懂,然后我发现网上的哪些大神原理讲的很明白,但代码没多少注释,看的很懵X,于是我抄起VS写了个详细注释版,真的很详细,史上最详细,全宇宙最详细,就这么自信,不信你看,看不懂你咬我。/*--------------------------------------------n* ...
noi1.11:09:膨胀的木棍:圆的认识
题目链接nn题目大意:nn有一横线,两端固定,会向上弯曲,求向上弯曲之后,中点的偏移量nn解题思路:nn1 又是一题非常简洁的题目,第一反应是跟圆弧之类的东西有关,于是就认真地理了一次公式nnnn2 根据以上的数学分析,夹角a和偏移量d是可以进行枚举的,具体的单调性等知识,请阅读以下博客:nnhttps://blog.csdn.net/txl199106/article/details/49332...
poj2653——Pick-up sticks(判断线段是否相交)
DescriptionStan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that th
sticks_backtracking
sticks cutting problem sticks are cut randomly until all parts became less than 50 units long. Now to return sticks to the original state. This program is designed to compute the smallest possible original length of those sticks.
北大2018acm暑期课五线段树
A Simple Problem with Integersnn描述nnYou have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given in...
uva10003 切木棍 线性区间dp
1. 线性dp,区间思想。n2. 动态转移方程:区间代价+此次的代价。n3. 下标i,j指的是切割点而不是每一个点。n4. 此次代价在底层可以直接返回结果。n5. 利用了标准的记忆化搜索模板,如果存在则返回。
UVA-10003 Cutting Sticks (动规-四边形不等式dp)
题目:nn          You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery, Inc. (ACM), charges money according to the length of the stick being cut. Their proc...
POJ 1011 Sticks(DFS+剪枝)详细注释
题目链接:http://poj.org/problem?id=1011Sticks nTime Limit: 1000MSMemory Limit: 10000K nTotal Submissions: 147064Accepted: 34847 nDescription nGeorge took sticks of the same length and cut them randomly unt
Sticks
Elistaniel is a very happy elf! He has found 4096 magic sticks! He has put them on the ground in one row so that every stick is parallel to each other. But there is one problem with magic sticks: In each second one of the sticks changes its state, which means that a parallel stick becomes normal and a normal stick becomes parallel (so the stick turns by 90 degrees).nnTASKnnYour task is to tell Elistaniel length of the longest sequence of sticks forming one line (sticks that have changed their state odd number of times) that occured during the observation time.nn nnINPUTnnThe firs line of input contains number t (1<=t<=20) - the number of test cases. Each test case begins with a single number n - meaning for how long Elistaniel has been watching the sticks. Then n lines follow. Number j in the i-th of the following lines means that in i-th second the j-th stick changed it state.nnOUTPUTnnFor each of test cases your program should write one number - length of the longest sequence of sticks forming a line.nnSAMPLEnnINPUTn1n6n1n3n5n2n4n3nnOUTPUTn5n
poj 1011 sticks(木棒) (dfs+剪枝)
Descriptionn n 乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。n n Input n 输入包含多组数据,每组数据包括两行。第一行是一个不超过64的整数,表示砍断之后
POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 怎么学习互联网大数据 村干部学习大数据心得