会员专享
请先
登录,登录后可使用今日免费解锁;
开通会员后可解锁完整内容。
枚举朴素解法
这道题的正解是 单调栈 贪心求字典序最大子序列,但是我们用朴素解法 暴力枚举所有长度为k的子序列取最大 也能在考试时拿到一定的分数。
题意:在保持相对顺序的前提下,从码流中选出恰好 k 个子包 ID,使得到的长度为 k 的序列字典序最大。输入若含非十进制数字字符则输出 error。
朴素做法:用 DFS / 回溯枚举「选或不选」当前元素,最终恰好选满 k 个,在所有候选中取字典序最大的那一个。时间约为 O(C(n,k)⋅k)。
样例和很小的 n 可以算对;当 n 接近 2000、且 k 不太小也不太大时组合数爆炸,会超时,需要后面的单调栈做法。