题目链接

题面：

题意：
有30001个岛屿，下标为0~30000，给ｎ个数告诉你有ｎ份宝藏藏在哪些岛上。

你从0往下标大的方向跳，第一步跳的距离为d。

如果上一步跳的距离为Ｄ，这一步就可以跳Ｄ-1或Ｄ或Ｄ+1（但是距离必须大于0）。

问最多拿到多少宝藏。

题解：
dp [ i ] [ j ] 表示跳到第 i 个岛屿上且前一步 跳跃距离为 d + j 的最大值。
因为每次只能增加1或者减少1，那么 d 往上波动不超250，往下波动不超250。
接下来线性递推就可以啦。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<set>
#define ll long long
#define pr make_pair
#define pb push_back
#define ui unsigned int
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define tlen(x) (t[(x)].r-t[(x)].l+1)
#define tmid (l+r)>>1
#define forhead for(int i=head[x];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1000000007;
const double eps=1e-8;
const double pi=acos(-1.0);
const int maxn=30100;
const int maxm=100100;
const int up=100000;

int dp[maxn][510];
int a[maxn];

int main(void)
{
    int n,d;
    scanf("%d%d",&n,&d);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        a[x]++;
    }
    int maxx=a[d];
    memset(dp,-1,sizeof(dp));
    dp[d][250]=a[d];
    for(int i=d;i<=30000;i++)
    {
        for(int j=1;j<=500;j++)
        {
            if(dp[i][j]==-1) continue;
            int dis=i+d+j-250;
            if(dis<=30000)
            {
                dp[dis][j]=max(dp[dis][j],dp[i][j]+a[dis]);
                maxx=max(maxx,dp[dis][j]);
            }
            if(dis+1<=30000)
            {
                dp[dis+1][j+1]=max(dp[dis+1][j],dp[i][j]+a[dis+1]);
                maxx=max(maxx,dp[dis+1][j+1]);
            }
            if(dis-1>i&&dis-1<=30000)
            {
                dp[dis-1][j-1]=max(dp[dis-1][j-1],dp[i][j]+a[dis-1]);
                maxx=max(maxx,dp[dis-1][j-1]);
            }
        }
    }
    printf("%d\n",maxx);
    return 0;
}