自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 21:18:37，当前版本为作者最后更新于2025-04-13 21:19:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

使用一维数组 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$ 时会发生数组越界。