(算法设计, 40分) 有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用c++写伪代码
时间: 2023-07-15 17:13:21 浏览: 41
算法思路:定义状态dp[i]表示以第i个矩形为结尾的最长可嵌套矩形序列长度,转移方程为dp[i]=max(dp[j])+1,其中j<i且第j个矩形可以嵌套在第i个矩形中。
伪代码如下:
```
for each test case {
read n
for i from 1 to n {
read a, b
rect[i] = (a, b)
}
sort rect in non-increasing order of a
for i from 1 to n {
dp[i] = 1
for j from 1 to i-1 {
if rect[j].b > rect[i].b and dp[j]+1 > dp[i] {
dp[i] = dp[j] + 1
}
}
}
print max(dp)
}
```
时间复杂度为O(n^2),其中n为矩形个数。
相关问题
有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到n,令dp[i]表示以第i个矩形为最外层矩形时能够嵌套的最大层数。那么状态转移方程为:
dp[i] = max(dp[j]) + 1, 其中j为所有能够嵌套在第i个矩形内部的矩形的编号。
如何判断矩形j能否嵌套在矩形i内部呢?我们可以分别判断矩形j顺时针旋转90度后能否嵌套在矩形i内部,以及矩形i顺时针旋转90度后能否嵌套在矩形j内部。只要其中一种情况成立,就说明矩形j能够嵌套在矩形i内部。
最终答案即为所有dp[i]中的最大值。
时间复杂度为O(n^2),空间复杂度为O(n)。