矩形嵌套
时间限制:3000 ms | 内存限制:65535 KB
难度:4
每组测试数据的第一行是一个正正数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
思路:
DP。一个矩形有长也有宽,固定把小的放左边,大的放右边,先对一边排序,再对另一边排序,排序后求最长上升子序列即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef struct { int l, w; } node; node no[1005]; int dp[1005]; bool cmp(node a, node b) { if (a.l != b.l) return a.l < b.l; return a.w < b.w; } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { int a, b; scanf("%d%d", &a, &b); no[i].l = min(a, b); no[i].w = max(a, b); } sort(no, no + n, cmp); int Max = 1; dp[0] = 1; for (int i = 1; i < n; ++i) { dp[i] = 1; for (int j = 0; j < i; ++j) { if (no[j].l < no[i].l && no[j].w < no[i].w && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; } Max = max(Max, dp[i]); } printf("%d\n", Max); } return 0; }
相关推荐
算法-矩形嵌套(NYOJ-16)(包含源程序).rar
利用数组打印嵌套的矩形框,该矩形框从中心开始,一圈矩形框,一圈空格。
矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形矩形...
标题化的目的是提供一种将嵌套列表转换为小标题的简便方法。 安装 您可以使用以下方法从安装tibblify的发行版本: install.packages("tibblify") 或使用以下命令从GitHub安装开发版本: # install.packages(...
划分一个由64块小正方形组成的8*8的矩形: 将原矩形分成两个矩形,在分开后的两个矩形中任选一块重复这样的划分, 这样分了(n-1)次后,连同最后剩下的矩形共有n块矩形。 原矩形上每一格有一个分值, 一块矩形的...
WPF工程 可绘制多个矩形 绘制结束后可拖动矩形的四个角 动态改变矩形大小
通过目标的对角点,可以框出目标的最小外接矩形
DOS界面,找图像中最大的轮廓、画外接矩形,计算矩形度
在 X-Y 坐标平面上,给定多个矩形,它们的边分别与坐标轴平行。请计算它们的并的面积。 输入格式 输入第一行为一个整数 n,1,表示矩形的数量。 接下来有 n 行,每行包括四个数:x1,y1,x2,y2 (0;0),用空格分开...
1097:画矩形 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 21249 通过数: 12589 【题目描述】 根据参数,画出矩形。输入四个参数:前两个参数为整数,依次代表矩形的高和宽(高不少于3行不多于10行,宽不少于5列...
Matlab实现的图像中的圆、矩形、正方形等形状识别
C#代码,不规则图形分割成多个矩形,可视化工具, 核心是一个找最大内切矩形的算法 牵涉到的知识点: 1. 图片的加载和像素解析,绘制到pictureBox上 2.控制pitctureBox缩放(ctrl+滚轮)和移动 3.动态生成bitmap,...
RectangleProgressView 矩形倒计时进度框 矩形进度框
qt 画矩形框、旋转矩形、先画直线、再画矩形、用于抠图
附件里是我的传输线和矩形波导的ppt,希望大家拍砖; 内容如下: 第四章 传输线理论 主 要 内 容 传输线的传输特性 (18)学时 4.1 引言 4.2 传输线方程及其解 4.3 传输线上波的传输特性参数 4.4 传输线的输入阻抗和...
圆变矩形课件圆变矩形课件圆变矩形课件圆变矩形课件圆变矩形课件圆变矩形课件圆变矩形课件圆变矩形课件
矩形类的定义,构造方法,访问属性等等矩形类的定义,构造方法,访问属性等等矩形类的定义,构造方法,访问属性等等矩形类的定义,构造方法,访问属性等等矩形类的定义,构造方法,访问属性等等矩形类的定义,构造...
java GUI awt 实现鼠标绘制矩形,鼠标拖动矩形,鼠标改变矩形大小功能. 其它图形的绘制方法参考: https://blog.csdn.net/xietansheng/article/details/55669157
在java编程环境下基于遗传算法的生成矩形件排样图
一个java程序,讲述矩形和一个圆的位置,主要是在不在矩形的内部