题目

Shuseki 群岛是 Yutampo 海中 30001 个小岛的群岛。这些岛沿一条线均匀分布，从西到东编号从 0 到 30000。
这些岛屿拥有许多宝藏。在 Shuseki 群岛***有 颗宝石，而第 颗宝石位于 岛上。（）

Kitayuta 先生刚到达 0 岛。凭借出色的跳跃能力，他将按照以下过程向东部的岛屿反复跳跃：

  • 首先，他将从岛 0 跳到岛 。（）
  • 之后，他将根据以下规则继续跳跃。
    令 为前一次跳跃的长度，即，如果他的前一次跳跃是从岛 到岛 ，则令 。
    他将向东进行长度为 ， 或 的跳跃。即他可以跳至岛 ， 或 （如果存在）。
    跳跃的长度必须为正数，即当 时，他不能执行长度为 0 的跳跃。
    如果没有有效的目的地，他将停止跳跃。

Kitayuta 先生将在此过程中到达过的岛屿上收集宝石。找到他可以收集的最大宝石数量。

解题思路

动态规划

表示前一次跳跃的长度是 ，到达岛屿 时收集的最大宝石数量。
那么，下一次跳跃长度 有 、、 这 3 中情况。
所以状态转移方程是 。
当然前提是 K 先生可以到达岛屿 ，即 。其中 表示岛屿 中宝石的数量。

假设第一步跳 1，后面每次增加 1 就可以求出最大的跳跃步长，计算 ，解得跳跃次数 ，所以最大跳不到 250 次，即跳跃长度最多在 的基础上增加 1 的次数不超过 250。
同理，假设第一步跳 249，后面每次减 1，到跳跃长度为 1 时已跳出整个群岛。因此， 的取值范围是 。

但 是数组的下标，不能取负值，所以给 一个偏移量 250，这样， 的取值范围就是 。
原来 表示前一次跳跃长度是 ，到达岛屿 时收集的最大宝石数量；给了偏移量后， 才是原来 表示的意思。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn = 30001;

int main(){
    int n, d;
    cin >> n >> d;
    vector<int> gems(maxn, 0);
    int pos;
    for(int i=0; i<n; ++i){
        cin >> pos;
        ++gems[pos];
    }

    int ans = gems[d];
    vector<vector<int>> dp(maxn, vector<int>(505, -1));
    dp[d][250] = ans;
    for(int i=d; i<maxn; ++i){
        for(int j=1; j<=500; ++j){
            if(dp[i][j]==-1) continue;
            pos = i + d + j - 250;
            for(int k=-1; k<=1; ++k){
                int next = pos + k;
                if(next>i && next<maxn){
                    dp[next][j+k] = max(dp[next][j+k], dp[i][j] + gems[next]);
                    ans = max(ans, dp[next][j+k]);
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}