A186078.双臂刻印
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
一条直线工作台上有 m 个位置,从左到右编号为 1∼m,相邻两个位置之间的距离为 1。
工作台上有 A、B 两只机械臂。它们最初分别位于位置 sA,sB,每移动一个单位距离分别消耗 cA,cB 点能量。
现在有 n 个刻印任务,必须按照给出的顺序依次完成。第 i 个任务要求在位置 xi 完成一次刻印。
完成一个任务时,必须选择其中一只机械臂:
- 将它从当前所在位置移动到任务要求的位置,再完成刻印;
- 若该机械臂原本就在目标位置,则无需移动,移动能耗为 0;
- 另一只机械臂保持原位;
- 刻印本身不消耗能量。
因此,A 臂从位置 u 移到位置 v 的能耗为 cA∣u−v∣,B 臂对应的能耗为 cB∣u−v∣。
每次任务结束后,两只机械臂都停留在各自所在的位置,供后续任务继续使用。任务之间不允许进行额外移动。
两只机械臂可以位于同一位置,也可以相互越过,不会发生碰撞或阻挡。相邻任务可以要求同一个位置,但每个任务仍须依次完成。全部任务完成后,机械臂无需返回初始位置。
请你选择每个任务由哪只机械臂完成,使总能耗尽可能小,并输出最小总能耗。
输入格式
第一行输入两个整数 n,m,分别表示任务数和工作台位置数。
第二行输入四个整数 sA,sB,cA,cB,分别表示 A、B 两臂的初始位置,以及各自每移动一个单位距离消耗的能量。
第三行输入 n 个整数 x1,x2,…,xn,表示按执行顺序排列的任务位置。
输出格式
输出一个整数,表示完成全部任务所需的最小总能耗。
输入输出样例
输入#1
4 10 1 10 1 2 2 9 3 8
输出#1
6
输入#2
2 10 1 10 1 10 9 10
输出#2
8
说明/提示
样例解释 1
依次让 A、B、A、B 臂执行四个任务:
- A 臂从 1 移到 2,消耗 1;
- B 臂从 10 移到 9,消耗 2;
- A 臂从 2 移到 3,消耗 1;
- B 臂从 9 移到 8,消耗 2。
总能耗为 6,可以证明不存在更小的总能耗。
样例解释 2
第一个任务由 A 臂执行,从 1 移到 9,消耗 8 点能量。第二个任务由 B 臂执行,它原本就在位置 10,无需移动。总能耗为 8。
虽然 B 臂离第一个任务更近,但它只要从 10 移到 9 就要消耗 10 点能量,因此按距离选择机械臂不一定最优。
数据范围
对于所有测试数据,保证:
- 1≤n≤2000;
- 1≤m≤1000;
- 1≤sA,sB,xi≤m;
- 1≤cA,cB≤109;
- 允许 sA=sB,允许多个任务位于同一位置。
输入解题思路,AI测评打分。不知道怎么写?