#P18952. [Mladen Manev 2022 AT2] play / 舞台道具搬运
[Mladen Manev 2022 AT2] play / 舞台道具搬运
舞台道具搬运
一条长为 的直线舞台的两端分别是位置 ,两端仓库都可无限供应和存放同一种道具。共有 幕演出,第 幕要求在给定的 个位置各放一件道具,其余舞台内部位置没有道具。
相邻两幕之间,可以移动道具,也可以从任一端仓库取出或送入道具。一次搬运一件道具,从位置 移到 的代价为 。空手走动不计代价。道具互相不可区分。
分别求从第 幕布置变为第 幕布置的最小总搬运代价,。
输入格式
第一行 。接下来 行,每行先给出 ,再给出严格递增的 个整数位置。
输出格式
输出 行,第 行是相邻两幕之间的最小代价。使用 64 位整数。
数据范围
,,,。每个位置 满足 。 时该行只有一个零。
样例
3 10
2 4 7
3 3 6 8
1 5
4
6
本题为波兰 XXVIII OI 决赛第一天 Les Bitérables(2021),由本网站 2022 年训练赛选用。
来源与数据说明
2022 年 Dr. Mladen Manev,AT2,原题名 play。赛事资料,原文题面见附件 statement.pdf。
原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。