Kupc2021_c题解 - Hanatomizu | Secret Base

[Hanatomizu]

https://hanatomizu.github.io/blog/post/kupc2021_c%E9%A2%98%E8%A7%A3/

题目传送门
思路
首先根据题目可以知道：
在最优解的情况下第 $i$ 个硬币在第 $i$ 个游戏机（题中的 Gacha）中使用。
题中 $B_j < B_{j+1} (1 \leq j \leq N-1)$ 可以得到。
整个移动过程可以视作为从 $0$ 开始向正方向移动，得到若干硬币后走回去玩没有玩的游戏机。
得出了以上结论，dp 的思路就清晰了。
设 $dp_i$ 为玩了前 $i$ 个游戏机时 $B_i$ 的最小值，$m$ 为玩了前 $i$ 个游戏机的迂回成本最小值。得到状态转移方程： $$m \gets \min(m, dp_{i-1} - A_i \times 2)$$ $$dp_i \gets \min(m, dp_{i-1} + B_i \times 2) + B_i \times 2$$
值得注意的是，对于 $A_i > B_i$ 的情况（即硬币在游戏机前面），可以直接忽略该硬币，把硬币的位置设置为游戏机的位置（即 $A_i \to B_i$）。因为在去往游戏机的路上一定会捡到该硬币。
得到答案为： $$ ans = \min(dp_n) + \min_{0 \leq i < n}(dp_i + B_n - A_{i+1}) + A_n $$