CF-4D普及+/提高
生日贺卡
⏱ 1.0s💾 64MB
📋 题目描述
胖球肚手里有 信封,编号从 到 ,每个信封的宽度分别为 ,每个信封的高度分别为 ,现在她要用这些信封制作一条链,这条链上的信封的尺寸有严格要求,后一个信封的宽度和高度分别要严格大于前一个信封的宽度和高度,链条大小为该链条上信封的数量,她要在这条链条上的信封里装入朋友的生日贺卡,贺卡的宽度为 ,高度为 ,卡片的宽度和高度必须分别小于链条中最小信封的宽度和高度。注意,信封和卡片都不能进行旋转。你的任务是帮助胖球肚确定可以获得链条的最大长度。
📥 输入格式
第一行包含三个整数 、、( , )表示胖球肚拥有的信封数量以及卡片的宽度和高度。接下来的 行,每行给出一个信封的大小,第 个信封的信息包含两个整数 和 表示该信封的宽度和高度( )。
📤 输出格式
第一行仅有一个整数 表示链条的最大长度,第二行给出最长链条上的 个信封的编号( 两两之间用一个空格分隔 ),从编号最小信封的编号开始输出。如果最长的链不唯一,输出任何一个方案即可。如果 则输出就没有第二行。
📝 样例 1
输入
2 1 1 2 2 2 2
输出
1 1
📝 样例 2
输入
3 3 3 5 4 12 11 9 8
输出
3 1 3 2
📚 来源
Problem:CF-4D
💡 题目讲解
1
理解题意
胖球肚过生日啦!她有 个信封,每个信封有宽度 和高度 。她想把信封一个套一个,做成一条"信封链",送给朋友。
套信封的规则:后面那个信封的宽和高,都要严格大于前面那个(等于不行哦)。
就像俄罗斯套娃一样,小的放进大的里:
链条里最小的那个信封,还要能装下一张生日贺卡(贺卡宽 、高 ,都要小于它的宽和高)。
🎯 我们要算:最长的"信封链"能有多长?并输出用了哪些信封的编号。
1 / 6