nyoj 题目16 矩形嵌套
2024-10-10 22:59:04
矩形嵌套
时间限制:3000 ms | 内存限制:65535 KB
难度:4
- 描述
- 有n个矩形,每个矩形可以用a,b来描述,表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转X90度)。例如(1,5)可以嵌套在(6,2)内,但不能嵌套在(3,4)中。你的任务是选出尽可能多的矩形排成一行,使得除最后一个外,每一个矩形都可以嵌套在下一个矩形内。
- 输入
- 第一行是一个正正数N(0<N<10),表示测试数据组数,
每组测试数据的第一行是一个正正数n,表示该组测试数据中含有矩形的个数(n<=1000)
随后的n行,每行有两个数a,b(0<a,b<100),表示矩形的长和宽 - 输出
- 每组测试数据都输出一个数,表示最多符合条件的矩形数目,每组输出占一行
- 样例输入
-
1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2 - 样例输出
-
5 转换为最长上升子序列问题,代码如下
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; typedef pair<int,int> Matrix;
Matrix mat[];
int cnt[]; bool cmp(Matrix a, Matrix b) {
if(a.first == b.first) {
return a.second < b.second;
}
else {
return a.first < b.first;
}
} bool isOk(Matrix a, Matrix b) {
return (a.first < b.first) && (a.second < b.second);
}
int main(int argc, char const *argv[])
{
int t;
//freopen("input.txt","r",stdin);
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
for(int i = ; i < n; i++) {
scanf("%d %d",&mat[i].first,&mat[i].second);
if(mat[i].first < mat[i].second) {
swap(mat[i].first,mat[i].second);
}
}
sort(mat,mat+n,cmp);
fill(cnt,cnt+n,);
int ans = ;
for(int i = ; i < n; i++) {
int maxv = ;
for(int j = i-; j >= ; j--) {
if(isOk(mat[j], mat[i]) && maxv < cnt[j]) {
maxv = cnt[j];
}
}
cnt[i] = maxv+;
if(ans < cnt[i]) {
ans = cnt[i];
}
}
printf("%d\n", ans); }
return ;
}
最新文章
- linux 查找文件和搜索文件
- Python的列表推导式,字典推导式,集合推导式使用方法
- Oracle补习班第七天
- java 配置文件读取
- Lingo 做线性规划 - DEA
- android fragment 博客 学习记录
- Windows 10 中 Eclipse中无法添加Courier New字体的解决方法!
- MVC&;WebForm对照学习:文件下载
- Trail: JDBC(TM) Database Access(2)
- OC 数据类型之间的转换方法
- 转 C#开发微信门户及应用(1)--开始使用微信接口
- Android为ListView的Item设置不同的布局
- hdu 1530 Maximum Clique
- hadoop工作平台梳理
- 炫酷的CSS3发光搜索表单,附演示和源码
- hdu_5832_A water problem(模拟)
- LNK2019解决思路
- Executor以及线程池
- Django--Auth 模块
- 4609: [Wf2016]Branch Assignment 最短路 DP (阅读理解题)
热门文章
- 阅读detection
- WIN10使用安装包安装Mysql5.6+JDBC
- PXE+DHCP+TFTP+Cobbler 无人值守安装centos 7
- scrapy--dytt(电影天堂)
- python简介,数据类型,input,if语句
- mysql替代like模糊查询的方法
- No module named &#39;PyQt5.sip&#39;
- openwrt(三) 固件的烧录
- vue 组件间数据传递
- 基于HDP版本的YDB安装部署(转)