题号 NC110793
名称 Mr. Kitayuta, the Treasure Hunter
来源 CF505C
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

设f[i][j]表示到达第i个岛屿，跳的距离为j 得到的最大宝藏数，那么转移方程为：
f[i+j][j] = max(f[i+j][j], f[i][j] + c[i+j])
f[i+j+1][j+1] = max(f[i+j+1][j+1], f[i][j] + c[i+j+1])
f[i+j-1][j-1] = max(f[i+j-1][j-1], f[i][j] + c[i+j-1])
如果开一个f[30000][30000]的数组的话会MLE(也会tle貌似)，这个时候我们需要多想一想。
由于最大步长是1+2+3+...a+250 > 30000。所以第二维最多在第一次的d的基础上上下浮动250（其实还没那么多），于是第二维开500就够了。
第二维的值x=250表示和d相等，(x - 250) + d 才是当前跳跃的距离orz！！

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目9月1日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴