有n个矩形,每个矩形可以用a,b来描述,表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转90度)。例如(1,5)可以嵌套在(6,2)内,但不能嵌套在(3,4)中。请设计一个动态规划算法选出尽可能多的矩形排成一行,使得除最后一个矩形外,每一个矩形都可以嵌套在下一个矩形内。(请先给出算法思路和递推式,再写伪代码,分析复杂度) 输入: 第一行是一个正数N(0<N),表示测试数据组数, 每组测试数据的第一行是一个正整数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
时间: 2023-07-15 18:12:51 浏览: 396
算法思路:
首先对所有矩形按照长和宽分别从小到大排序,方便后续处理。用 dp[i] 表示以第 i 个矩形为结尾的符合条件的矩形数目,转移时枚举前面能够嵌套的矩形,选择其中 dp[j] 最大的一个进行转移,即:
$$
dp[i]=\max\limits_{j=1}^{i-1}\{dp[j]\}+1, j<i \text{ 且矩形 j 能够嵌套在矩形 i 中}
$$
最终答案即为 $\max\limits_{i=1}^n\{dp[i]\}$。
时间复杂度:$O(n^2)$。
伪代码:
sort(rectangles) // 按照长和宽从小到大排序
for i=1 to n:
dp[i]=1
for j=1 to i-1:
if rectangle[j] 能够嵌套在 rectangle[i] 中:
dp[i]=max(dp[i], dp[j]+1)
ans=max(dp[1...n])
print ans
其中,判断矩形 j 能够嵌套在矩形 i 中的方法可以根据题目要求实现,这里不再赘述。
相关问题
有n个矩形,每个矩形可以用a,b来描述,表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转90度)。
这是一个经典的矩形嵌套问题,可以通过贪心算法来解决。具体步骤如下:
1. 将所有矩形按照长或宽的大小排序,即将所有矩形按照max(a,b)从小到大排序。
2. 从小到大遍历每个矩形X,尝试将其嵌套在已有的矩形Y中。
3. 对于每个矩形X,从已有的矩形中选择一个可以嵌套的矩形Y,并且使嵌套后的面积最大。
4. 如果找不到可以嵌套的矩形Y,就将X作为一个新的矩形加入到已有的矩形中。
5. 重复步骤2-4,直到所有矩形都被处理完毕。
6. 最终已有的矩形就是最大的矩形集合。
这个算法的时间复杂度是O(nlogn),其中n是矩形的个数。
有n个矩形,每个矩形可以用a,b来描述,表示长和宽。矩形x(a,b)可以嵌套在矩形y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转90度)。例如(1,5)可以嵌套在(6,2)内,但不
可以嵌套在(3,4)内。现在给定n个矩形,请你找出其中最多可以嵌套多少个矩形。
解题思路:
1. 首先将所有矩形按照长和宽从小到大排序,这样可以保证后面的矩形可以嵌套在前面的矩形中。
2. 定义一个数组dp,dp[i]表示以第i个矩形为最外层矩形时,最多可以嵌套多少个矩形。
3. 对于每个矩形i,枚举前面的所有矩形j,如果矩形i可以嵌套在矩形j中,则更新dp[i]为dp[j]+1。
4. 最终答案为dp数组中的最大值。
代码实现:
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)