Wooden Sticks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11249 Accepted Submission(s): 4629
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
Source Asia 2001, Taejon (South Korea)
Recommend We have carefully selected several similar problems for you: 1050 2037 1052 1045 1009
在POJ呆惯了，WA一直以为是代码问题，没想到是数组开小了。。。。
这道题关键在于为什么贪心可以找到最优解。
刚开始我不懂，为什么用贪心可以找出最优解！也在这个问题上纠结了很久，感觉比较痛苦！
这和找最长递增子序列不同，只要能加入到原有的序列中比新开一个递增子序列，所得到的子序列数一定更少。
#include
#include
using namespace std
; #define M 11000
struct node
{ int l
,w
; }f
[M
]; int vis
[M
]; //将长度排序，降低成为一位数组的扫描。 bool cmp
(node a
,node b
){ if(a
.l
<b
.l
) return true
; if(a
.l
>b
.l
) return false
; if(a
.l
==b
.l
) return a
.w
<b
.w
; } int main() { int n
,m
,t
,i
,j
,cur
,tot
; while(scanf
("%d"
,&n
)!=EOF
) { while(n
--) { cur
=0
;tot
=0
; memset
(vis
,0
,sizeof(vis
)); scanf
("%d"
,&m
); for(i
=0
;i
<m
;i
++) { scanf
("%d%d"
,&f
[i
].l
,&f
[i
].w
); } sort
(f
,f
+m
,cmp
); for(i
=0
;i
<m
;i
++) { if(vis
[i
]) continue; //如果已经排入一个递增子序列，就不用再考虑。 t
=f
[i
].w
;vis
[i
]=1
; for(j
=i
+1
;j
<m
;j
++) { if(!vis
[j
]&&t
<=f
[j
].w
) //找递增子序列的元素。 { vis
[j
]=1
; t
=f
[j
].w
; } } tot
++; } printf
("%d\n"
,tot
); } } return 0
; }
|