测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A7008. 神秘的礼物

编程题 普及/提高-

题目描述

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$ 个信封的宽度和高度。

输出格式

第一行输出一个整数,表示最长信封链的长度。

第二行输出组成该链的信封编号(按从小到大的顺序,即从最里面的信封到最外面的信封),编号之间用空格分隔。

如果存在多个长度最大的方案,输出任意一个即可。
如果没有任何信封能装下卡片,则在第一行输出 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 3 2

**【数据范围】**

* $1 \le n \le 5000$
* $1 \le w, h, w_i, h_i \le 10^6$
上一题 去做题 下一题