| 题目名称 | 1243. 嵌套矩形 |
|---|---|
| 输入输出 | qiantao.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 王者自由
于2012-11-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：85， 提交：157， 通过率：54.14% | ||||
 ┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
|
ムラサメ |
100 | 0.000 s | 0.00 MiB | C++ |
 AntiLeaf |
100 | 0.011 s | 0.59 MiB | C++ |
 吉羊旋律 |
100 | 0.012 s | 1.48 MiB | C++ |
 サイタマ |
100 | 0.013 s | 1.26 MiB | C++ |
 Arrow |
100 | 0.013 s | 1.30 MiB | C++ |
 Hzoi_ |
100 | 0.015 s | 0.59 MiB | C++ |
 xxcxcxcx |
100 | 0.017 s | 1.26 MiB | C++ |
 father |
100 | 0.019 s | 1.26 MiB | C++ |
| 关于 嵌套矩形 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
1
| ||||
|
我的错觉:似乎加点优化能上榜?
| ||||
|
递归真慢!
 AAAAAAAAAA
2016-11-15 16:30
9楼
| ||||
|
偷懒写个floyd不仅T了还WA了身败名裂系列。
| ||||
|
| ||||
|
记忆化搜索
| ||||
|
记忆化搜索+字典序 OvO
| ||||
|
我排序了。。不會用記錄父節點的來按字典序輸出路徑。。最後改用vector記錄整個路徑。。。
 Makazeu
2012-11-03 13:17
4楼
| ||||
|
尿了。。不會按字典序輸出路徑
Makazeu
2012-11-03 12:59
3楼
| ||||
|
我刚才看看DAG_DP的定义，赶脚“最长XX子序列”一类的问题也是DAG_DP。
Makazeu
2012-11-03 11:12
2楼
| ||||
snake
sxysxy
liu_runda
残镖书生
raywzy【题目描述】
有 n 个矩形，每个矩形可以用两个整数 a, b 描述，表示它的长和宽。矩形 X(a, b) 可以嵌套在矩形 Y(c, d) 中当且仅当 a<c, b<d，或者 b<c, a<d（相当于把矩形 X 旋转了 90°）。例如 (1, 5) 可以嵌套在 (6, 2) 内，但不能嵌套在 (3, 4) 内。
你的任务是选出尽量多的矩形，使得除了最后一个之外，每一个矩形都可以嵌套在下一个矩形内。
【输入格式】
第一行一个正整数 n (n <= 1000)。
接下来 n 行每行两个正整数 a, b 表示矩形 i 的长和宽。
【输出格式】
第一行一个整数 k 表示符合条件的最多矩形数。
第二行 k 个整数依次表示符合条件矩形的编号，要求字典序最小。
【样例输入】
8 14 9 15 19 18 12 9 10 19 17 15 9 2 13 13 10
【样例输出】
4 4 8 3 2
【样例说明】
最大嵌套深度为 4 。
4 个矩形分别是：4(9, 10) < 8(13, 10) < 3(18,12) < 2(15,19)
【来源】
算法竞赛入门经典 例题 9-2