DP_Wooden Sticks
2019-08-16 07:57:35来源:博客园 阅读 ()
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:现代c++与模板元编程
- POJ 1011 Sticks解题报告 2018-08-17
- poj 1011--Sticks(搜索) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash