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

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（贪心）

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+剪枝）

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,

ZOJ 1025 Wooden Sticks 【思维 + 最长下降子序列 + Dilworth定理】

【POJ-2452】Sticks Problem【二分右端点+线段树】

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 动态规划之求下降子序列的个数。

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的条数)

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

HDU 1051 Wooden Sticks （贪心 + 读不懂题目系列）

poj 1065 Wooden Sticks (求最长非降子序列的个数）

POJ 1065 Wooden Sticks 最长不上升子集 偏序定理

POJ - 1065 Wooden Sticks 贪心+最长上升子序列

POJ1127 Jack Straws（判断线段相交+Floyd-Warshall求传递闭包）

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: ←...

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（搜索问题）

noi1.11：09：膨胀的木棍：圆的认识

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.

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）

POJ 1011 Sticks（DFS+剪枝）详细注释

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】