← 返回题目列表

Codeforces · 1866/E

E. Tamem 电梯

中文机器翻译题面 查看原题

有一座名为 Taman Membeku(简称 Tamem)的建筑物。该建筑有 $$$N$$$ 楼​​层,从下到上编号为 $$$1$$$ 到 $$$N$$$。在建筑物各楼层之间移动的唯一方法是使用电梯。 Tamem 有 $$$3$$$ 电梯,即电梯 $$$1$$$、$$$2$$$ 和 $$$3$$$。

Pak Chanek 在 Tamem 担任电梯操作员。 Pak Chanek 将工作 $$$Q$$$ 天。最初,每部电梯位于 $$$1$$$ 层,并且所有电梯均已开启。每一天,都会发生以下其中一种情况:

- 1 x y – 目前在 $$$x$$$ 楼层有人想要前往 $$$y$$$ 楼层。 ($$$1\leq x,y\leq N$$$; $$$x\neq y$$$)
- 下午 2 点 – 电梯 $$$p$$$ 在一天开始时更改状态。如果之前它是打开的,那么它将关闭。如果之前它是关闭的,那么它将打开。 ($$$1\leq p\leq3$$$)

Pak Chanek 每天都可以随心所欲地控制所有电梯的运行。然而,对于当前位于 $$$x$$$ 楼层的每一天,想要前往 $$$y$$$ 楼层的人,在 Pak Chanek 执行的所有电梯移动中,必须发生以下情况:

1. 一部电梯移至 $$$x$$$ 层。
2. 该人进入电梯。
3. 电梯移至楼层 $$$y$$$。
4. 该人走出电梯。

Pak Chanek 每天只能移动当前运行的电梯。请注意,由于状态变化发生在一天开始时,这意味着在某一天关闭的电梯从那天起就开始变得无法使用。相反,某天开启的电梯从那天起就开始可用。

据了解,每天的电费是不同的。更具体地,在第$$$j$$$天,将一部电梯向上或向下移动一层所需的费用为$$$A_j$$$。

从一开始,Pak Chanek 就已经知道电费以及 $$$Q$$$ 日将发生的事件顺序,因此 Pak Chanek 可以有策略地操作电梯。满足想要在 Tamem 楼层之间移动的人们的所有需求的最低电费是多少?注意:最后每部电梯不必返回$$$1$$$层。

输入

第一行包含两个整数 $$$N$$$ 和 $$$Q$$$ ($$$2\leq N\leq10^5$$$; $$$1\leq Q\leq300$$$) — 楼层数和天数。

第二行包含 $$$Q$$$ 整数 $$$A_1, A_2, A_3 \ldots, A_Q$$$ ($$$1 \leq A_j \leq 10^5$$$) — 每天的电费。

接下来的 $$$Q$$$ 行中的第 $$$j$$$ 行包含所描述的第 $$$j$$$ 事件。在任何时刻,总会至少有一部电梯处于运行状态。

输出

一个整数,表示满足想要在 Tamem 楼层之间移动的人员的所有需求的最低可能电费。

示例

输入 #1

9 8
3 4 4 3 4 2 7 6
1 2 7
1 3 9
2 2
1 4 5
1 3 5
2 2
1 7 3
1 2 1

输出 #1

114

注意

以下是最佳策略的示例:

1. 在 $$$1$$$ 第一天:电梯 $$$2$$$ 移动到楼层 $$$3$$$。 电梯 $$$3$$$ 移动到 $$$2$$$ 楼​​层,接人,移动到 $$$7$$$ 楼​​层,然后送人下车。
2. 在第 $$$2$$$ 天:电梯 $$$2$$$ 接人,移动到楼层 $$$9$$$,然后送人下车。
3. 在第 $$$3$$$ 天:电梯 $$$2$$$ 关闭。
4. 在第 $$$4$$$ 天:电梯 $$$3$$$ 移动到楼层 $$$4$$$,接人,移动到楼层 $$$5$$$,放下人,然后移动到楼层 $$$3$$$。
5. 在第 $$$5$$$ 天:电梯 $$$3$$$ 接人,移动到楼层 $$$5$$$,然后送人下车。
6. 在第 $$$6$$$ 天:电梯 $$$2$$$ 打开。 电梯 $$$1$$$ 移动到楼层 $$$2$$$。 电梯 $$$2$$$ 移动到楼层 $$$7$$$。
7. 在第 $$$7$$$ 天:电梯 $$$2$$$ 接人,移动到楼层 $$$3$$$,然后送人下车。
8. 在第 $$$8$$$ 天:电梯 $$$1$$$ 接人,移动到楼层 $$$1$$$,然后送人下车。

从第$$$1$$$日到第$$$8$$$日,每天的总电费分别为$$$24$$$、$$$24$$$、$$$0$$$、$$$18$$$、$$$8$$$、$$$6$$$、$$$28$$$和$$$6$$$。因此整个$$$Q$$$天的总电费为$$$24+24+0+18+8+6+28+6=114$$$。

可以得出,不存在需要更小的电费的策略。