题解

普通的 DP 很容易想出来，刷表法就行了。

优化：注意到每一次跳跃的距离永远在 $[d-400,d+400]$ 之间，所以优化成 $O(800N)$ 能过了。

为什么？

我不知道啊，感觉是一个神秘的东西。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=3e4+34;
ll n,m,x,y,z,ans;
ll a[MAXN];
unordered_map<ll,ll> dp[MAXN];
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>x;
        a[x]++;
    }
    dp[m][0]=a[m];
    for(ll i=m;i<=30000;i++){
        for(ll j=-400;j<=400;j++){
            x=m+j;
            if(x<=0||!dp[i].count(j)) continue;
            for(ll k=-1;k<=1;k++){
                y=x+k;
                if(y<=0) continue;
                z=i+y;
                if(z<=30000){
                    dp[z][j+k]=max(dp[i][j]+a[z],dp[z][j+k]);
                    ans=max(dp[i][j]+a[z],ans);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}