题解

首先来一个正常的 DP：

$dp[i][j]$ 记录在第 $i$ 格，当 $l=j$ 时收集宝石的最大值。

显然递推式如下：

$$dp[i][j]=max(dp[i-j][j-1],dp[i-j][j],dp[i-j][j+1])+b_i$$

其中 $b_i$ 为第 $i$ 格的宝石数，并且要保证 $i-j\ge m$。

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int a[5005], b[5005], dp[5005][5005];
int n, m, mx;
signed main(){
	memset(dp, -64, sizeof(dp));
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i], b[a[i]]++;
	dp[m][m] = b[m];
	for(int i = m + 1; i <= 5000; i++){
		for(int j = 1; j <= i - m; j++){
			dp[i][j] = max(max(dp[i - j][j - 1], dp[i - j][j]), dp[i - j][j + 1]) + b[i];
			mx = max(mx, dp[i][j]);
		}
	}
	cout << mx;

	return 0;
}

时间复杂度：$O(a_i\times (a_i-d))$。

得分：$70pts$。​

这对于 $a_i\le 3\times 10^4$ 的数据还是太吃操作了，怎么优化呢？

注意到在 $3\times 10^4$ 格内，跳跃过程中 $l$ 的取值范围很小，一定在 $d\pm 300$ 的范围内，也就是说上面的 $dp$ 存在大量无效状态。

根据上面的推理，我们可以把 $dp$ 的第二维的大小减少到 $601$，$dp[i][j]$ 表示第 $i$ 格，当 $l=j+d-301$ 时收集宝石的最大值。将上面的状态转移方程稍加改变即可。

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int a[30005], b[30005], dp[30005][615];
//(d-300)~(d+300) 
int n, m, mx;
signed main(){
	memset(dp, -64, sizeof(dp));
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i], b[a[i]]++;
	dp[m][301] = b[m];
	for(int i = m + 1; i <= 30000; i++){
		for(int j = 1; j <= 601; j++){
			int realj = j + m - 301;
			if(realj < 1 || realj > i) continue;
			dp[i][j] = max(max(dp[i - realj][j - 1], dp[i - realj][j]), dp[i - realj][j + 1]) + b[i];
			mx = max(mx, dp[i][j]);
		}
	}
	cout << mx;

	return 0;
}

时间复杂度：$O((a_i-d)\times \sqrt{a_i})$。

得分：$100pts$。