DP_Wooden Sticks
2024-09-05 05:57:30
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 ) .
(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
排序时在长度相同的情况下应优先按照宽度再次进行排序。
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[];
struct Node{
int h,w;
}p[];
bool cmp( Node a, Node b){
if( a.h!=b.h )
return a.h<b.h ? true:false;
return a.w<b.w ? true:false;
}
int main()
{
int t,n;
int maxn; scanf("%d",&t);
while( t-- ){
maxn=;
scanf("%d",&n);
for( int i=; i<n; i++)
scanf("%d%d",&p[i].h,&p[i].w);
sort( p, p+n, cmp);
for( int j=; j<n; j++)
dp[j]=;
for( int i=; i<n; i++){
for( int j=; j<i; j++){
if( p[j].w>p[i].w ){
dp[i]=max(dp[i],dp[j]+);
}
}
}
for( int i=; i<n; i++)
if( dp[i]>maxn )
maxn=dp[i];
printf("%d\n",maxn);
} return ;
}
感谢SLH的耐心讲解
最新文章
- C#6新特性,让你的代码更干净
- 自动将指定目录下面的文件转换为UTF-8
- Oracle 环境变量NLS_LANG
- 图的基本遍历算法的实现(BFS &; DFS)复习
- 网格测地线算法(Geodesics in Heat)附源码
- dev gridcontrol纵向合并单元格设置
- android:scaleType属性
- 使用 Entity Framework
- Cygwin下设置ls显示颜色
- 2014年度辛星html教程夏季版第二节
- XSS解决方案系列之四:关于编码
- Xcode7修改模块生成网络权限(ATS配置)
- Windows下MySQL分步安装图解及问题总结
- Redis集群以及自动故障转移测试
- 进程&;线程(转)
- Run Redis
- [翻译]EntityFramework Core 2.2 发布
- 帝国cms面包屑导航的首页链接锚文本改成关键字
- learning ddr mode register MR0
- beta圆桌 SUM UP