AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

P3830. 乘坐保密电梯

中等通过率 29% · 提交 228 · 通过 66
回溯背包DP动态规划排序

小慕正在开发一个智能电梯调度系统,用于一栋保密大楼。他从0楼出发,需要到达指定楼层m,电梯必须按照如下规则运行: 给定一个数字序列,每次根据序列中的数字n,电梯可以上升n层或者下降n层,但前后两次的运行方向必须相反,且规定第一次运行方向必须向上。小慕可以自行调整序列中数字的顺序,使得电梯按照上述规则最终停靠在目标楼层。 小慕需要找出能够到达目标楼层的序列组合。如果无法恰好到达,则输出小于该楼层的最近楼层所对应的序列组合。

提示:带虚线的词点一下有通俗解释。

输入描述

第一行:期望的楼层,取值范围[1,50]; 序列总个数,取值范围[1,23] 第二行:序列,每个值取值范围[1,50]

输出描述

能够达到楼层或者小于该楼层最近的序列

示例

示例 1

输入

5 3
1 2 6

输出

6 2 1

说明:1 2 6,6 2 1均为可行解,按先处理大值的原则结果为6 2 1

时间限制 2000 ms · 内存限制 128 MB

看不懂题目?点开图解
0 1 2 3 起点0 +6 -2 +1 目标5 图例 上升 下降 目标楼层
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「乘坐保密电梯」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。