题解：B4317 [语言月赛 202504] 金币收集

· · 题解

本题考察二维数组的应用。

首先我们要存储输入的信息。

使用一维数组 mv[100005] 来记录所有移动，使用二维数组 p[1005][1005] 来记录第 j 次到达区域 i 时的奖励，和题目定义一致。p 的第二个维度大小应该略大于 t_i 的最大可能值，这样才能确保不会溢出。

然后我们模拟 yummy 的移动即可。我们用 cur 表示当前 yummy 的位置，coin 表示 yummy 获得的硬币总数。

注意 coin 应该是 long long 类型，因为 coin 最大可能值是 10^9\times 10^5，超过了 int 的范围。

同时，为了计算奖励，我们还需要一个数组 v[1005] 来记录每个区域已经到达了几次。每次更新完位置 cur 后，要先把 cur 的次数增加 1；然后如果 v[cur]<=t[cur] 那么加上对应的奖励 p[cur][vis[cur]] 即可。

注意：这个判断是必不可少的，否则当 v[cur] 远大于 1000 时会发生数组越界。