P17896 [ICPC 2026 Nanchang I] Gotta Go Fast

题目描述

你玩过蛋仔派对吗?inf 很喜欢玩蛋仔派对。 四个蛋仔叠成一个四层高的蛋仔柱,初始底部位于坐标 $0$。从下到上依次记为 A、B、C、D,其中 D 是最顶端的蛋仔。 赛道总长度为 $l$,包含 $l$ 段长度为 $1$ 的线段,线段 $i$ 连接坐标 $i-1$ 和 $i$ $(1 \le i \le l)$。 第 $i$ 段线段的地形由字符 $S_i$ 给出。若蛋仔柱从坐标 $i-1$ 走到坐标 $i$,需要花费: - 平地 `0`:$t_0$ 秒; - 泥潭 `1`:$t_1$ 秒; - 加速带 `2`:$t_2$ 秒。 蛋仔柱可以进行两种操作: - **普通前进:** 若当前蛋仔柱位于坐标 $x < l$,则可整体前进至坐标 $x+1$。这次前进的耗时**只与第 $x+1$ 段地形有关**。 - **超级起步:** 若当前坐标 $x$ 处有一个包含 $j$ 个蛋仔的蛋仔柱 $(j \ge 2)$,则最底部的蛋仔可以把上面的 $j-1$ 个蛋仔瞬间扔到坐标 $\min(l, x+d)$,其中 $d$ 为一个给定的正整数。这个操作不触发地形耗时,即耗时为 $0$。操作后,原地最底部的蛋仔被淘汰,原位置变为空;坐标 $\min(l, x+d)$ 处形成一个包含 $j-1$ 个蛋仔的新蛋仔柱,剩余蛋仔的上下顺序保持不变。 请计算让初始时最顶端的蛋仔 D 到达终点坐标 $l$ 所需要的最短时间。

输入格式

第一行包含两个正整数 $l$ 和 $d$ ($1 \le d < l \le 2 \times 10^5$)。 第二行包含三个正整数 $t_0$, $t_1$, $t_2$ ($1 \le t_2 < t_0 < t_1 \le 10^9$)。 第三行包含一个长度为 $l$ 的字符串 $S$,仅由字符 `0`、`1`、`2` 组成。

输出格式

输出一个整数,表示最短总时间。

说明/提示

对于样例一:一种最优方案是连续发动 $3$ 次超级起步到达坐标 $6$,再走完最后 $4$ 段平地,总耗时为 $4 \times 10 = 40$。 对于样例二:一种最优方案是先连续两次超级起步到达坐标 $6$,步行走过 $3$ 段加速带到达坐标 $9$,最后再超级起步到终点,总耗时为 $1+1+1=3$。 对于样例三:一种最优方案是先走过前 $3$ 段加速带和 $1$ 段平地到达坐标 $4$,再连续发动 $3$ 次超级起步到达终点,总耗时为 $1+1+1+10=13$。 对于样例四:连续发动 $3$ 次超级起步,坐标变化为 $0\to 3\to 6\to 8$(最后一次触发 $\min (8, 6+3)$ 限制),全程不需要步行,总耗时为 $0$。