HDU 1051 Wooden Sticks 贪心||DP

时间:2022-01-20 03:10:04

Wooden Sticks

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 22000    Accepted Submission(s): 8851

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
思路:将木棒按l,w 递减的顺序排列,统计关于递减的连续子列的个数即为答案。
代码:
 #include "cstdio"
 #include "iostream"
 #include "algorithm"
 #include "string"
 #include "cstring"
 #include "queue"
 #include "cmath"
 #include "vector"
 #include "map"
 #include "stdlib.h"
 #include "set"
 #define mj
 #define db double
 #define ll long long
 using  namespace std;
 ;
 ;
 ;
 bool u[N];
 typedef  struct stu{
     int l,w;
 }M;
 M s[];
 int cmp(M a,M b)
 {
     if(a.l==b.l) return a.w>=b.w;
     return a.l>=b.l;
 }
 int main()
 {
     int t,n,i,j,ans;
     scanf("%d",&t);
     while(t--)
     {
         scanf("%d",&n);
         ;i<n;i++)
             scanf(;
         sort(s,s+n,cmp);
         int mi;
         ans=;
         ;i<n;i++)
         {
             if(u[i]) continue;
             mi=s[i].w;
             ;j<n;j++)
             {
                 if(!u[j]&&s[j].w<=mi){
                     mi=s[j].w;
                     u[j]=;
                 }
             }
             ans++;
         }
         printf("%d\n",ans);
     }
     ;
 }
 

HDU 1051 Wooden Sticks 贪心||DP的更多相关文章

  1. HDU 1051 Wooden Sticks &lpar;贪心&rpar;

    Wooden Sticks Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) To ...

  2. HDU - 1051 Wooden Sticks 贪心 动态规划

    Wooden Sticks Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)    ...

  3. HDU 1051 Wooden Sticks 贪心题解

    本题一看就知道是最长不减序列了,一想就以为是使用dp攻克了. 只是那是个错误的思路. 我就动了半天没动出来.然后看了看别人是能够使用dp的,只是那个比較难证明其正确性,而其速度也不快.故此并非非常好的 ...

  4. hdu 1051 wooden sticks &lpar;贪心&plus;巧妙转化)

    #include <iostream>#include<stdio.h>#include<cmath>#include<algorithm>using ...

  5. hdu 1051&colon;Wooden Sticks(水题,贪心)

    Wooden Sticks Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Tot ...

  6. HDOJ 1051&period; Wooden Sticks 贪心 结构体排序

    Wooden Sticks Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) To ...

  7. HDOJ&period;1051 Wooden Sticks &lpar;贪心&rpar;

    Wooden Sticks 点我挑战题目 题意分析 给出T组数据,每组数据有n对数,分别代表每个木棍的长度l和重量w.第一个木棍加工需要1min的准备准备时间,对于刚刚经加工过的木棍,如果接下来的木棍 ...

  8. HDU 1051 Wooden Sticks 造木棍【贪心】

    题目链接>>> 转载于:https://www.cnblogs.com/Action-/archive/2012/07/03/2574800.html  题目大意: 给n根木棍的长度 ...

  9. HDU 1051 Wooden Sticks

    题意: 有 n 根木棒,长度和质量都已经知道,需要一个机器一根一根地处理这些木棒. 该机器在加工过程中需要一定的准备时间,是用于清洗机器,调整工具和模板的. 机器需要的准备时间如下: 1.第一根需要1 ...

随机推荐

  1. WaitType:SOS&lowbar;SCHEDULER&lowbar;YIELD

    今天遇到一个query,处于SOS_SCHEDULER_YIELD 状态,physical IO 不增加,CPU的使用一直在增长.当一个sql query长时间处于SOS_SCHEDULER_YIEL ...

  2. MIT jos 6&period;828 Fall 2014 训练记录(lab 5)

    源代码参见我的github: https://github.com/YaoZengzeng/jos File system perliminaries 我们开发的是一个单用户的操作系统,只提供了足够的 ...

  3. Android中的音频播放(MediaPlayer和SoundPool)

    Android中音频和视频的播放我们最先想到的就是MediaPlayer类了,该类提供了播放.暂停.停止.和重复播放等方法.该类位于android.media包下,详见API文档.其实除了这个类还有一 ...

  4. IPV6与IPV4的区别

    IPv4协议的地址长度是32位,IPv6协议的地址长度是128位. 1.表示方式 IPv4地址表示为点分十进制格式,32位的地址分成4个8位分组,每个8位以十进制数显式,中间用点号分隔. 而IPv6采 ...

  5. Internal类

    C#中一个类中的成员有四种修饰级别: public:完全开放,谁都能访问. private:完全封闭,只有类自身可以访问. internal:只对相同程序集,或使用InternalVisibleToA ...

  6. FastStone Capture激活码

    用户名:c1ikm注册码:AXMQX-RMMMJ-DBHHF-WIHTV 或 AXOQS-RRMGS-ODAQO-APHUU

  7. python学习笔记——(三)文件操作

    ·集合操作及其相应的操作符表示集合中没有插入,只有添加,因为毕竟无序 #!/usr/bin/env python # -*- coding:utf-8 -*- # Author:Vergil Zhan ...

  8. 理解es6中的const与&OpenCurlyDoubleQuote;不变”

    const实际上保证的,并不是变量的值不得改动,而是变量指向的那个内存地址不得改动. 效果 对于简单类型的数据(数值.字符串.布尔值),值就保存在变量指向的那个内存地址,因此等同于常量. 对于复合类型 ...

  9. JavaScript日期排序

    //日期排序 function sortDownDate(a, b) { return Date.parse(a.received) - Date.parse(b.received); } funct ...

  10. XML解析技术简介——(一)