A7008. 神秘的礼物
编程题
普及/提高-
知识点
题目描述
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$