题解

这题讲一个叫做根号分治的Tips，以空间换时间最直观的一集。

首先拿到题第一个想到暴力骗分:），考虑我们的搜索算法，发现可以贪心：对于到达一个点$x$，步长为$l$，我们只需要知道最多能拿多少个宝石。

因此考虑用$BFS$+记忆化搜索去做这道题，发现时间复杂度近似为$O(N^2 / d *log(N^2/d) )$。当d>900的时候，用$BFS$+记忆化搜索是可以通过此题的。

现在思考这样一个问题：在$BFS$的过程，我们会遇到很多次点为$x$，步长为$l$的状态，这样其实花费了大量的时间。于是窝们考虑设计一个记忆化函数：$dp[i][j]$ ， 代表了到达点$i$，步长为$j$所能拿到的最多宝石个数。

有了函数后考虑设计状态转移：
$dp[i + j + 1][j + 1] = max(dp[i + j + 1][j + 1] ,dp[i][j] + a_{i + j + 1})$
$dp[i + j][j] = max(dp[i + j][j] ,dp[i][j] + a_{i + j })$
$dp[i + j - 1][j - 1] = max(dp[i + j - 1][j - 1] ,dp[i][j] + a_{i + j - 1})$

这样做的话时间复杂度是$O(N^2)$

如果只考虑$dp$的话，我们将会把数组开到$dp[N][N]$，这显然是不能够接受的，于是我们就想到了：当$d$足够大的时候，只需要按照$BFS$+记忆化搜索解决就可以了，这样就可以大大的减少我们的第二维。也就是开头说的：当$d>900$时考虑暴力、然后通过$dp$预处理出$d<900$的所有答案。这样$dp$数组的第二维只需要开到$1000$。时间复杂度为$O(N*1000 + N^2 / 1000 *log(N^2/1000))$

（本题的所有$d＜100$）

#include<bits/stdc++.h>
using namespace std;
const int B = 1000;
const int N = 30001;
//根号分治
int a[N] = {0};
int ans = 0;
set<array<int,3>>st;//位置从小到大，步长从小到大，答案从大到小
map<array<int,2>,int>mp;
void bfs(int x) {
    st.insert({0 , x , -a[0]});
    while (!st.empty()) {
        array<int,3> tmp = *st.begin();
        int pos = tmp[0] , step = tmp[1] , cnt = -tmp[2];
        st.erase(tmp);
        if (mp.count({pos , step})) continue;
        mp[{pos , step}] = cnt;
        for (int i = -1 ; i <= 1 ; i ++) {
            int new_step = step + i;
            if (new_step == 0) continue;
            int new_pos = pos + new_step;
            if (new_pos >= N) {
                ans = max(ans , cnt);
                continue;
            }
            int new_cnt = cnt + a[new_pos];
            st.insert({new_pos , -new_cnt});
        }
    }
}
int main() {
    int n , k;
    cin >> n >> k;
    for (int i = 0 ; i < n ; i ++) {
        int x;
        cin >> x;
        a[x]++;
    }
    if (k > B - 100) {
        bfs(k);
        cout << ans << endl;
        return 0;
    }
    vector< vector < int > > dp(N + 5 , vector< int > (B  , -10000000));
    dp[k][k] = a[k];
    for (int i = 0 ; i < N ; i ++) {
        for (int j = 1 ; j < B ; j ++) {
            if (i + j < N)
                dp[i + j][j] = max(dp[i + j][j] , dp[i][j] + a[i + j]);
            if (j - 1 > 0 && i + j - 1 < N) {
                dp[i + j - 1][j - 1] = max(dp[i + j - 1][j - 1] , dp[i][j] + a[i + j - 1]);
            }
            if (j + 1 < B && i + j + 1 < N) {
                dp[i + j + 1][j + 1] = max(dp[i + j + 1][j + 1] , dp[i][j] + a[i + j + 1]);
            }
        }
    }
    for (int i = 0 ; i < N ; i ++) {
        for (int j = 0 ; j < B ; j ++) {
            ans = max(ans , dp[i][j]);
        }
    }
    cout << ans << endl;
}