这个问题据说是dp问题,不过我觉得只用到了一点
dp知识,先把矩形排序,宽对应宽长对应长;然后
对宽或者长进行排序(二级排序),再找出另一方的最大上升子
序列,即可。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
# define maxn 1000
int cmp(const void *a,const void *b)
{
int* c = (int *)a;
int* d = (int *)b;
if(*c != *d)
return *c - *d;
return *(d+1) - *(c+1);
}
int main()
{
int a[maxn+10][5];
int b[maxn+10];
int t,n,i,j,temp;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&a[i][0],&a[i][1]);
if(a[i][0] > a[i][1])
{
temp = a[i][0];
a[i][0] = a[i][1];
a[i][1] =temp;
}
}
qsort(a,n,sizeof(a[0]),cmp);
int max=0;
for(i=0;i<n;i++)
{ max = 0;
for(j=i-1;j>=0;j--)
{
if(a[j][1]<a[i][1] && b[j]>max)
max = b[j];
}
b[i] = max + 1;
}
int count = 0;
for(i=0;i<n;i++)
if(b[i] > count)
count = b[i];
printf("%d\n",count);
}
return 0;
}
分享到:
相关推荐
算法-矩形嵌套(NYOJ-16)(包含源程序).rar
利用数组打印嵌套的矩形框,该矩形框从中心开始,一圈矩形框,一圈空格。
标题化的目的是提供一种将嵌套列表转换为小标题的简便方法。 安装 您可以使用以下方法从安装tibblify的发行版本: install.packages("tibblify") 或使用以下命令从GitHub安装开发版本: # install.packages(...
VB画图例子,Line方法画矩形 VB代码例子,虽然简单,参考学习挺有用的: Private Sub Form_Load() Show ... Line (4000 - i, 1000 - i)-(4000 i, 1000 i), , B '画嵌套方形 Next i End Sub
计算机视觉是机器准确识别、理解和表示信息,从而感知并与世界交互的媒介,在人脸识别、智能驾驶、手势游戏、图像搜索、自动定位等各领域都发挥着极为重要的作用。OpenCV作为开源程序库,提供了500多个用于图像和...
基于OpenCV的二维矩形绘制,C++代码,代码基于OpenCV库实现二维矩形的绘制,且包含注释,适合初学者练习使用
使用嵌套for循环实现用*生成任意大小的矩形形、任意大小的镂空的矩形、任意大小的三角形、任意大小的镂空三角形
树形图使用嵌套矩形的相对区域显示数据。 有关更多信息,请参阅http://en.wikipedia.org/wiki/Treemapping 。
##自举网格生成器## 通过在任何网站上绘制矩形来创建引导行/列网格! ###如何安装?### 安装 chrome 扩展: : ... 您可以在彼此内部绘制矩形以嵌套行和列。 但不要绘制部分相交的矩形(即内外矩形)
Canvas 中文名称叫“画布”,它是游戏中所有UI组件...一个场景中,可以允许多个Canvas对象的存在,还允许Canvas之间可以进行“嵌套”使用。需要注意的是,场景中的任何一个UI对象,都肯定是某个Canvas对象的“子级”。
用for循环嵌套循环的方式,输出一行9个“*”,共计9行的矩形图形
嵌套矩形js 在Javascript中绘制n个具有不同颜色(数组)的嵌套矩形 例子 document.body.appendChild(addRect(15));
C的空心菱形
问题 关联 1 一维数组的运行总和 2 子矩形查询 3 洗牌 4 好的对数 5 拥有最多糖果的孩子 6 defanging-an-ip-地址 7 多少个数字比当前数字小 8 解压缩运行长度编码列表 9 按指定顺序创建目标数组 10 数组中的异或运算...
React嵌套滑块(WIP) 演示版 查看在线 或在本地运行: yarn install yarn storybook 要求 单击轨道名称左侧的右矩形时,应该具有“折叠/展开” 应该能够拖动过渡栏,左过渡处理程序和右过渡处理程序来更改延迟和...
最大的矩形 嵌套对象 哈希表追踪 哈希集 缓存 旋转 桶排序 分布式文件系统 BFS 堆 树集 跟踪最小值/最大值并更新结果 流(双端队列/缓存/堆/树集) 排序 间隔 实现数据结构 特里 段树和二叉索引树 图(主要是拓扑...
Canvas中绘制直线、矩形、椭圆等各种几何图形,也可绘制图片、文字、UI组件(如Button)等。Canvas 允许重新改变这些图形项(Tkinter将程序绘制的所有东西统称为item)的属性,比如改变其坐标、外观等。Canvas组件的...
在给定一个矩形底板和以及一些字母材料时,如何将这些字母材料尽可能的塞进这个矩形底板并且保持字母两两之间并不会重合?通过一些特殊的摆放顺序与位置以及将每个字母旋转到合适的角度,我们可以达到这个目的。而...
GoNest 2D是一种 嵌套 软件,用于生成优化的 布局 并减少二维矩形切割(断头台切割或嵌套)工艺产生的 废料 。可应用于各种行业,例如玻璃切割,板材金属布局和制造,木材加工,建筑面板,地毯,PCB,丙烯酸树脂等。...