16.[NOIP2009 普及组] 道路游戏 难度：普及- 来源：-- AC代码（C#）： 没有注释，自行学习。 by：yanghaozhe Tips： 代码中的： 实际是指： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 你的点赞和关注就是我更新题解的最大动力！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ -----------------------------点个赞吧 ↓ ！-----------------------------

作者没有焯

用一维数组f储存第i秒能获得的最大钱数 因为最多同时存在1个机器人 第i秒时第j个机器人走k次(1<=k<=p) f[i]=max(f[i],f[i-k]-pay[last]+sum) 这里是从当前点倒推 last是上一个点 当last=0,last=n sum要一遍遍加上钱k秒第last路上的金币数 每次减去第last条道路（即第last个工厂机器人）的价格 如果i-k<0 直接退出k循环，时间不为负 因为结果可能是负的 初始化为-99999999 f[0]=0，即第0秒金币数为0 输出第m秒的值

玩暗区突围的私信我

这个题有点过于生草了，好不容易想出前缀和来，前缀和里还有大坑 sum[a][b]表示一个机器人以 工厂a 为起点，从第一秒走到第 b 秒拾到的金币， 但是 sum[k][i]-sum[k][j]表示的却不是以k为起点， sum[k][i]-sum[k][j]表示的是以k+j 为起点的 从第 j+1 秒到第 i 秒捡到的所有金币， 因为当第一秒的起点固定时，随着时间的推移，时间也变了，位置也变了 简直是自找麻烦 再来看看别人的代码，过于生草了，确实明白自己是有多自找麻烦了 AC代码

前言：这™不是蓝题吗，提高+，怎么成了橙

加油，继续去肝下一题 ~