POJ 1065 Wooden Sticks Greed,DP
2024-08-21 05:57:23
排序后贪心或根据第二关键字找最长下降子序列
#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 ;
}
最新文章
- Yii2-多表关联的用法示例
- 【腾讯Bugly干货分享】安卓单元测试:What, Why and How
- codevs4096 删数问题
- awk 手册--【转载】
- Java之面向对象相关问题集
- 要点Java17 String
- virtualbox 中安装win7虚拟机
- Apache 服务器
- MS-SQL 错误: The offset specified in a OFFSET clause may not be negative
- ASP.NET Core MVC请求超时设置解决方案
- asp.net core使用Swashbuckle.AspNetCore(swagger)生成接口文档
- Docker容器跨主机通信
- java String转int int转化为String
- oralce问题
- hdu 4506 快速幂
- FPGA中亚稳态相关问题及跨时钟域处理
- 在本地SharePoint 2013 搭建App开发环境
- 前端 -----02 body标签中相关标签
- Sonya and Problem Wihtout a Legend CodeForces - 714E (dp)
- react与fetch