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$。