POJ 1065 Wooden Sticks Greed,DP

时间:2023-01-02 22:07:32

排序后贪心或根据第二关键字找最长下降子序列

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cmath>
#include<climits>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define pb(a) push(a)
#define INF 0x1f1f1f1f
#define lson idx<<1,l,mid
#define rson idx<<1|1,mid+1,r
#define PI 3.1415926535898
template<class T> T min(const T& a,const T& b,const T& c) {
return min(min(a,b),min(a,c));
}
template<class T> T max(const T& a,const T& b,const T& c) {
return max(max(a,b),max(a,c));
}
void debug() {
#ifdef ONLINE_JUDGE
#else freopen("in.txt","r",stdin);
freopen("d:\\out1.txt","w",stdout);
#endif
}
int getch() {
int ch;
while((ch=getchar())!=EOF) {
if(ch!=' '&&ch!='\n')return ch;
}
return EOF;
} const int maxn=;
struct node
{
int l,w;
bool operator < (const node &ant) const
{
return l<ant.l||l==ant.l&&w<ant.w;
}
};
node da[maxn];
int vis[maxn];
int main()
{
int t;
scanf("%d", &t);
for(int ca = ; ca <= t; ca++)
{
int n;
scanf("%d", &n);
for(int i = ; i < n; i++)
scanf("%d%d", &da[i].l, &da[i].w);
sort(da, da + n);
memset(vis,,sizeof(vis));
int res=;
for(int cnt=;;)
{
res++;
int curl=-,curw=-;
for(int i=;i<n;i++)
{
if(!vis[i]&&da[i].l>=curl&&da[i].w>=curw)
{
vis[i] = ; cnt++;
curl=da[i].l;curw=da[i].w;
}
}
if(cnt==n)break;
}
printf("%d\n",res);
}
return ;
}

POJ 1065 Wooden Sticks Greed,DP的更多相关文章

  1. POJ 1065 Wooden Sticks &sol; hdu 1257 最少拦截系统 DP 贪心

    参考链接:http://blog.csdn.net/xiaohuan1991/article/details/6956629 (HDU 1257 解题思路一样就不继续讲解) POJ 1065题意:给你 ...

  2. POJ 1065 Wooden Sticks

    Wooden Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 16262 Accepted: 6748 Descri ...

  3. HDU ACM 1051&sol; POJ 1065 Wooden Sticks

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

  4. POJ 1065 Wooden Sticks (贪心)

    There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The st ...

  5. poj -1065 Wooden Sticks (贪心or dp)

    http://poj.org/problem?id=1065 题意比较简单,有n跟木棍,事先知道每根木棍的长度和宽度,这些木棍需要送去加工,第一根木棍需要一分钟的生产时间,如果当前木棍的长度跟宽度 都 ...

  6. POJ - 1065 Wooden Sticks(贪心&plus;dp&plus;最长递减子序列&plus;Dilworth定理)

    题意:给定n个木棍的l和w,第一个木棍需要1min安装时间,若木棍(l’,w’)满足l' >= l, w' >= w,则不需要花费额外的安装时间,否则需要花费1min安装时间,求安装n个木 ...

  7. POJ 1065 Wooden Sticks(zoj 1025) 最长单调子序列

    POJ :http://poj.org/problem?id=1065 ZOJ: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId= ...

  8. poj 1065 Wooden Sticks 【贪心 新思维】

    题目地址:http://poj.org/problem?id=1065 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 ...

  9. POJ 1065 Wooden Sticks【贪心】

    题意: 有一些木棍,每个有长度和重量,要求把这些木棍排成若干两个属性值均不下降的序列.问至少要分为多少个序列.且要保证排出来的子序列数最少. 思路: ( 9 , 4 ) ,( 2 , 5 ) ,( 1 ...

随机推荐

  1. SVN的目录说明

    subversion目录说明:*dav目录:是提供apache与mod_dav_svn使用的目录,让他们存储内部数据*db目录:就是所有版本控制的数据存放文件*hooks目录:放置hook脚本文件的目 ...

  2. jq 获取table元素,ajax 静态填加数据

    知识点: 1.jq如何操作table->操作html内的元素 2. this 怎么使用 问题: 1.点击 修改 后,自动刷新了.判断取值,提示错误.正确出不来 2.ajax传值操作如何保密 ht ...

  3. Android(java)学习笔记257:JNI之helloword案例(利用NDK工具)

    1.逻辑思路过程图: 2.下面通过一个HelloWorld案例来说明一下JNI利用NDK开发过程(步骤) 分析:我们在Win7系统下编译的C语言代码,我们知道C语言依赖操作系统,不能跨平台,所以我们要 ...

  4. 如何使用 Barracuda 防火墙设置&sol;保护 Azure 应用程序

     如果某企业在 Windows Azure 上托管某个应用程序,该应用程序会在某个特定时间暴露到 Internet,以用于商业用途.公共 Internet 带来 客户的同时也带来了攻击者. Tim ...

  5. VS2015 scanf 函数报错 error C4996&colon; &&num;39&semi;scanf&&num;39&semi;

    错误提示:error C4996: 'scanf': This function or variable may be unsafe. Consider using scanf_s instead. ...

  6. loj 诗歌

    链接 链接 思路 好久之前的考试题了吧,之前貌似抄的题解 现在理解了怕忘了,就写个题解记录一下吧,题目还是不错的 枚举中间点j \[H_{i}-H_{j}=H_{j}-H_{k}\] \[H_{k}+ ...

  7. java 转载

    这几天忙于其他的事情,编程的习惯没有继续下去,偶然间看到了这篇文章,感觉收益颇丰,言归正传,下面即入主题 java基础知识小总结 在一个独立的原始程序里,只能有一个 public 类,却可以有许多 n ...

  8. OC与JS交互之WKWebView

    上一篇文章我们使用了JavaScriptCore框架重写了之前的示例,iOS8苹果偏爱HTML5,重构了UIWebVIew,给我们带来了WKWebView,使其性能.稳定性.功能大幅度提升,也更好的支 ...

  9. 【整理总结】Visual Studio 扩展和更新

    Add New File File Icons C# outline ClaudiaIDE Code alignment CodeMaid Indent Guides Inline Color Pic ...

  10. mysql 存储过程案列一个。

    -- 设置分隔符 DELIMITER // /*初始化*/ DROP PROCEDURE IF EXISTS useCursor // /*建立 存储过程 create */ CREATE PROCE ...