C++(g++ 7.5.0) 解法, 执行用时: 310ms, 内存消耗: 120460K, 提交时间: 2022-11-21 17:00:01

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e4+10,M=300;
ll dp[N][510],w[N];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int len,d;
    cin>>len>>d;
    for(int i=1;i<=len;i++){
        int x;
        cin>>x;
        w[x]++;
    }
    memset(dp,-0x3f,sizeof dp);
    dp[d][260]=w[d];
    ll ans=w[d];
    for(int i=1;i<=N-10;i++){
        for(int j=-250;j<=250;j++){
            int p=d+j,z=260+j;
            if(p<=0) continue;
            if(p>i) continue;
            dp[i][z]=max(dp[i][z],dp[i-p][z+1]+w[i]);
            dp[i][z]=max(dp[i][z],dp[i-p][z]+w[i]);
            if(p) dp[i][z]=max(dp[i][z],dp[i-p][z-1]+w[i]);
            ans=max(ans,dp[i][z]);
        }
    }
    cout<<ans;
}

C++(clang++ 11.0.1) 解法, 执行用时: 143ms, 内存消耗: 60392K, 提交时间: 2022-10-06 15:27:47

#include<bits/stdc++.h>
#define qq 30005
#define pq 255
using namespace std;
int a[qq],dp[qq][pq<<1],n,d,x;
int main(){
    cin>>n>>d;
    for(int i=1;i<=n;++i) scanf("%d",&x),++a[x];
    memset(dp,-0x3f,sizeof(dp));
    dp[d][pq]=a[0]+a[d];
    for(int i=0;i<=30000;++i){
        for(int j=-250;j<=250;++j){
            if(i-(d+j)<0 || i-(d+j)>30000) continue;
            dp[i][j+pq]=max(dp[i][j+pq],max(dp[i-(d+j)][j+pq],max(dp[i-(d+j)][j-1+pq],dp[i-(d+j)][j+1+pq]))+a[i]);
        }
    }
    int ans=0;
    for(int i=0;i<=30000;++i)for(int j=-250;j<=250;++j)ans=max(ans,dp[i][j+pq]);
    cout<<ans;
    return 0;
}