DP_Wooden Sticks

2019-08-16 07:57:35来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

DP_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 ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .

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 2n 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



题意:求同时满足木棒的长宽都构成不下降子序列的最少组数。

思路:1、将木棒按照长(或宽)进行升序排序。
   2、建立递推数组dp[],表示操作当前木棒时所需要的设定次数。
   3、dp[]的递推公式:  若前面存在一个木棒的宽度大于当前木棒的宽度的时,当前木棒所需要进行的设置数一定会大于这个木棒所需要的设置数。
           当前木棒的dp[]=max{dp[前面宽度大于当前木棒宽度的木棒所对应的下标]}+1
   4、遍历数组dp[],最大的dp即为题目所求最少需要的设定次数.
注意:排序完成后的木棒默认只设定一次(即假设排序完成后的序列为一个不下降序列)dp[]值初始化为1
   排序时在长度相同的情况下应优先按照宽度再次进行排序。




 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int dp[5005];
 5 struct Node{
 6     int h,w;
 7 }p[5005];
 8 bool cmp( Node a, Node b){
 9     if( a.h!=b.h )
10         return a.h<b.h ? true:false;
11     return a.w<b.w ? true:false;
12 }
13 int main()
14 {
15     int t,n;
16     int maxn;
17 
18     scanf("%d",&t);
19     while( t-- ){
20         maxn=1;
21         scanf("%d",&n);
22         for( int i=0; i<n; i++)
23             scanf("%d%d",&p[i].h,&p[i].w);
24         sort( p, p+n, cmp);
25         for( int j=0; j<n; j++)  
26             dp[j]=1;
27         for( int i=0; i<n; i++){
28             for( int j=0; j<i; j++){
29                 if( p[j].w>p[i].w ){
30                     dp[i]=max(dp[i],dp[j]+1);
31                 }
32             }
33         }
34         for( int i=0; i<n; i++)
35             if( dp[i]>maxn )
36                 maxn=dp[i];
37         printf("%d\n",maxn);
38     }
39 
40     return 0;
41 }
View Code

 



感谢SLH的耐心讲解


原文链接:https://www.cnblogs.com/konoba/p/11295475.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:「中山纪中集训省选组D2T1」书堆 欧拉常数

下一篇:现代c++与模板元编程