A186078.双臂刻印

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

一条直线工作台上有 mm 个位置,从左到右编号为 1∼m1\sim m,相邻两个位置之间的距离为 11。

工作台上有 A、B 两只机械臂。它们最初分别位于位置 sA,sBs_A,s_B,每移动一个单位距离分别消耗 cA,cBc_A,c_B 点能量。

现在有 nn 个刻印任务,必须按照给出的顺序依次完成。第 ii 个任务要求在位置 xix_i 完成一次刻印。

完成一个任务时,必须选择其中一只机械臂:

  • 将它从当前所在位置移动到任务要求的位置,再完成刻印;
  • 若该机械臂原本就在目标位置,则无需移动,移动能耗为 00;
  • 另一只机械臂保持原位;
  • 刻印本身不消耗能量。

因此,A 臂从位置 uu 移到位置 vv 的能耗为 cA∣u−v∣c_A|u-v|,B 臂对应的能耗为 cB∣u−v∣c_B|u-v|。

每次任务结束后,两只机械臂都停留在各自所在的位置,供后续任务继续使用。任务之间不允许进行额外移动。

两只机械臂可以位于同一位置,也可以相互越过,不会发生碰撞或阻挡。相邻任务可以要求同一个位置,但每个任务仍须依次完成。全部任务完成后,机械臂无需返回初始位置。

请你选择每个任务由哪只机械臂完成,使总能耗尽可能小,并输出最小总能耗。

输入格式

第一行输入两个整数 n,mn,m,分别表示任务数和工作台位置数。

第二行输入四个整数 sA,sB,cA,cBs_A,s_B,c_A,c_B,分别表示 A、B 两臂的初始位置,以及各自每移动一个单位距离消耗的能量。

第三行输入 nn 个整数 x1,x2,…,xnx_1,x_2,\ldots,x_n,表示按执行顺序排列的任务位置。

输出格式

输出一个整数,表示完成全部任务所需的最小总能耗。

输入输出样例

  • 输入#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 臂从 11 移到 22,消耗 11;
  • B 臂从 1010 移到 99,消耗 22;
  • A 臂从 22 移到 33,消耗 11;
  • B 臂从 99 移到 88,消耗 22。

总能耗为 66,可以证明不存在更小的总能耗。

样例解释 2

第一个任务由 A 臂执行,从 11 移到 99,消耗 88 点能量。第二个任务由 B 臂执行,它原本就在位置 1010,无需移动。总能耗为 88。

虽然 B 臂离第一个任务更近,但它只要从 1010 移到 99 就要消耗 1010 点能量,因此按距离选择机械臂不一定最优。

数据范围

对于所有测试数据,保证:

  • 1≤n≤20001\le n\le2000;
  • 1≤m≤10001\le m\le1000;
  • 1≤sA,sB,xi≤m1\le s_A,s_B,x_i\le m;
  • 1≤cA,cB≤1091\le c_A,c_B\le10^9;
  • 允许 sA=sBs_A=s_B,允许多个任务位于同一位置。

输入解题思路,AI测评打分。不知道怎么写?

首页