题解 | #宝藏猎人#

由于到达下一点只可能产生{1,0,-1}的变化;

假设一直递降, 即操作为d, d-1, d-2, d-3, ..为等差数列.

设极限情况末尾速度为0, 即路程和为(n-1)*n/2 <= 30000 -> 求得n<300;

取n=300, 暴力枚举下复杂度为30000300(长度每点情况) = 9*10^6, 不会超时.

//
// Created by HASEE on 2024/5/9.
//

/*** remain true to the original aspiration ***/
#include <bits/stdc++.h>

using namespace std;

// #pragma GCC optimize(2)
// #pragma G++ optimize(2)

#define pli pair<li, li>
#define ll long long
#define li long long
#define int long long
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define Test   \
    ll ___;    \
    read(___); \
    while (___--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define Faster                     \
    ios_base ::sync_with_stdio(0); \
    cin.tie(0);                    \
    cout.tie(0);
#define YES printf("YES\n");
#define Yes printf("Yes\n");
#define NO printf("NO\n");
#define No printf("No\n");
int mod = 1e9 + 7;
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * (b / gcd(a, b)))
#define popcount(x) __builtin_popcount(x)
#define string(x) to_string(x)
int dx[] = {-1, 0, 0, 1, 0}; // ��������
int dy[] = {0, -1, 1, 0, 0};
int dx1[] = {-1, -1, -1, 0, 1, 0, 1, 1, 0}; // ���� ���� ���� �� �� �� ���� ���� ����
int dy1[] = {-1, 0, 1, -1, 1, 1, -1, 0, 0};
int dx2[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy2[] = {-1, 1, -2, 2, -2, 2, -1, 1};

const ll INF = 0x3f3f3f3f;
const double PI = 3.141592653589793238462643383279;

ll powmod(ll a, ll b)
{
    ll res = 1;
    a %= mod;
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

ll square(ll x1, ll y1, ll x2, ll y2) { return abs(x2 - x1) * abs(y2 - y1); }

ll get_dist(ll x1, ll y1, ll x2, ll y2) { return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); }

ll get_jiao(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4)
{
    int n1 = max(min(x1, x2), min(x3, x4)), m1 = max(min(y1, y2), min(y3, y4)), n2 = min(max(x1, x2), max(x3, x4)), m2 = min(max(y1, y2), max(y3, y4));
    if (n2 > n1 && m2 > m1)
        return (n2 - n1) * (m2 - m1);
    else
        return 0;
}

template <typename T>
inline bool read(T &x)
{
    x = 0;
    int f = 1;
    char c = getchar();
    bool ret = false;
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c <= '9' && c >= '0')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
        ret = true;
    }
    x = x * f;
    return ret;
}

template <typename T, typename... Args>
inline bool read(T &a, Args &...args) { return read(a) && read(args...); }

template <typename T, typename Type>
inline void print(T x, const Type type)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        print(x / 10, 0);
    putchar(x % 10 ^ 48);
    if (type == 1)
        putchar(' ');
    else if (type == 2)
        putchar('\n');
}

template <typename T, typename Type, typename... Args>
inline void print(T x, const Type type, Args... args)
{
    print(x, type);
    print(args...);
}
// #define rint register int
#define rint int
#define rep(i, i0, n) for (rint i = i0; i <= n; i++)
#define per(i, in, i0) for (rint i = in; i >= i0; i--)
#define itn int
#define PII pair<int, int>
///______________________ L E T ' S  B E G I N _____________________

const int N=1e5+7;
const int m=260;
int a[N]={};
int f[30010][2*m+7];

signed main()
{
    int n,d;
    read(n,d);
    rep(i,1,n){
        int x;
        read(x);
        a[x]+=1;
    }
    memset(f, -0x3f, sizeof f);
    f[d][m]=a[0]+a[d];
    int res=a[d]+a[0];
    rep(i,d+1,30000)
    rep(j,-m,m){
        int pre=d+j;
        if(pre>=0&&i-pre>=0) {
            int tmp = -0x7fffffff;
            tmp = max(tmp, f[i - pre][j - 1+m]);
            tmp = max(tmp, f[i - pre][j + 1+m]);
            tmp = max(tmp, f[i - pre][j+m]);
            f[i][j+m] = tmp + a[i];
        }
        res=max(res,f[i][j+m]);
    }
    print(res,2);
}