A7008 | 神秘的礼物
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Peter 决定给他住在澳大利亚的朋友写一张生日贺卡。为了让这份礼物显得更加神秘，他决定用一系列的信封制作一个“信封套娃链”。
这里的“链”是指一个信封序列 $A = \{a_1, a_2, \dots, a_k\}$，其中第 $i$ 个信封的宽度和高度必须**严格大于**第 $i-1$ 个信封的宽度和高度。序列的长度即为链中信封的个数。
Peter 想要从他拥有的信封中选出一些，组成一个长度最大的链。同时，这个链必须能够装下他准备的卡片。卡片能装入链中的条件是：卡片的宽度和高度必须**严格小于**链中最小信封（即 $a_1$）的宽度和高度。
**注意：** 信封和卡片都**不能旋转**。
Peter 有很多信封但时间紧迫，于是他把这个艰巨的任务交给了你。请你计算出满足条件的最长信封链的长度，并输出具体的信封编号序列。
这里的“链”是指一个信封序列 $A = \{a_1, a_2, \dots, a_k\}$，其中第 $i$ 个信封的宽度和高度必须**严格大于**第 $i-1$ 个信封的宽度和高度。序列的长度即为链中信封的个数。
Peter 想要从他拥有的信封中选出一些，组成一个长度最大的链。同时，这个链必须能够装下他准备的卡片。卡片能装入链中的条件是：卡片的宽度和高度必须**严格小于**链中最小信封（即 $a_1$）的宽度和高度。
**注意：** 信封和卡片都**不能旋转**。
Peter 有很多信封但时间紧迫，于是他把这个艰巨的任务交给了你。请你计算出满足条件的最长信封链的长度，并输出具体的信封编号序列。
输入格式
第一行包含三个整数 $n, w, h$ ($1 \le n \le 5000$, $1 \le w, h \le 10^6$)，分别表示 Peter 拥有的信封数量、卡片的宽度和高度。
接下来的 $n$ 行，每行包含两个整数 $w_i$ 和 $h_i$ ($1 \le w_i, h_i \le 10^6$)，表示第 $i$ 个信封的宽度和高度。
接下来的 $n$ 行，每行包含两个整数 $w_i$ 和 $h_i$ ($1 \le w_i, h_i \le 10^6$)，表示第 $i$ 个信封的宽度和高度。
输出格式
第一行输出一个整数，表示最长信封链的长度。
第二行输出组成该链的信封编号（按从小到大的顺序，即从最里面的信封到最外面的信封），编号之间用空格分隔。
如果存在多个长度最大的方案，输出任意一个即可。
如果没有任何信封能装下卡片，则在第一行输出
第二行输出组成该链的信封编号（按从小到大的顺序，即从最里面的信封到最外面的信封），编号之间用空格分隔。
如果存在多个长度最大的方案，输出任意一个即可。
如果没有任何信封能装下卡片，则在第一行输出
0。输入输出样例
输入 #1
2 1 1 2 2 2 2
输出 #1
1 1
输入 #2
3 3 3 5 4 12 11 9 8
输出 #2
3 1 3 2
**【样例解释 1】**
* **卡片尺寸**：$1 \times 1$。
* **信封 1**：$2 \times 2$。能装下卡片（$2>1, 2>1$）。
* **信封 2**：$2 \times 2$。能装下卡片。
* **尝试建链**：
* 如果我们选信封 1 作为第一层，信封 2 能套在信封 1 外面吗？不能。因为题目要求**严格大于**，而 $2$ 不大于 $2$。
* 同理，信封 1 也不能套在信封 2 外面。
* **结论**：最长链长度为 1。输出编号 1（或者 2）。
**【样例解释 2】**
* **卡片尺寸**：$3 \times 3$。
* **信封 1**：$5 \times 4$。能装下卡片。
* **信封 2**：$12 \times 11$。能装下卡片。
* **信封 3**：$9 \times 8$。能装下卡片。
* **最优链构造**：
1. 最内层：信封 1 ($5 \times 4$)。
2. 中间层：信封 3 ($9 \times 8$)。因为 $9 > 5$ 且 $8 > 4$，可以套在信封 1 外面。
3. 最外层：信封 2 ($12 \times 11$)。因为 $12 > 9$ 且 $11 > 8$，可以套在信封 3 外面。
* **路径**：卡片 $\to$ 1 $\to$ 3 $\to$ 2。
* **结果**：长度为 3，顺序为
**【数据范围】**
* $1 \le n \le 5000$
* $1 \le w, h, w_i, h_i \le 10^6$
* **卡片尺寸**：$1 \times 1$。
* **信封 1**：$2 \times 2$。能装下卡片（$2>1, 2>1$）。
* **信封 2**：$2 \times 2$。能装下卡片。
* **尝试建链**：
* 如果我们选信封 1 作为第一层，信封 2 能套在信封 1 外面吗？不能。因为题目要求**严格大于**，而 $2$ 不大于 $2$。
* 同理，信封 1 也不能套在信封 2 外面。
* **结论**：最长链长度为 1。输出编号 1（或者 2）。
**【样例解释 2】**
* **卡片尺寸**：$3 \times 3$。
* **信封 1**：$5 \times 4$。能装下卡片。
* **信封 2**：$12 \times 11$。能装下卡片。
* **信封 3**：$9 \times 8$。能装下卡片。
* **最优链构造**：
1. 最内层：信封 1 ($5 \times 4$)。
2. 中间层：信封 3 ($9 \times 8$)。因为 $9 > 5$ 且 $8 > 4$，可以套在信封 1 外面。
3. 最外层：信封 2 ($12 \times 11$)。因为 $12 > 9$ 且 $11 > 8$，可以套在信封 3 外面。
* **路径**：卡片 $\to$ 1 $\to$ 3 $\to$ 2。
* **结果**：长度为 3，顺序为
1 3 2。**【数据范围】**
* $1 \le n \le 5000$
* $1 \le w, h, w_i, h_i \le 10^6$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？