Mr. Kitayuta, the Treasure Hunter - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
一眼为DP
该如何考虑dp状态？显然到了 第 i 个点的时候，还需要知道达到此时走的步的大小,才能进行dp转移
考虑dp[i][j]为这次走了j大步走到i能获得最多的宝藏，但这回MLE
考虑优化空间大小，显然位置是不容易优化的，尽量优化第二维数组的空间
最坏的结果是第一步 为 1，则 1+2+3+4+...+n>30001→n=260 ，此时最大的步数也仅仅是 260
对于其他第一步大于1的，最后最大的步数只可能更小，最小步数逆这来同理。
所以对于任何步数 x，d为题目给出的的第一步，则x-d∈[-300,300]
令M=300，所以x-d+M属于[0,2*M]，这种数据范围就很适合作为第二维dp的空间大小
枚举时，第一重循环 i 依旧为第一维度，第二重循坏 j 为第二维度，j=x-d+M；
则 x=j+d-M;根据题目要求要保证x>=1;
转移方程：
dp[i+x][j]=max(dp[i+x][j],dp[i][j]+a[i+x]) （i+x<=m&&x>=1）
dp[i+x+1][j+1]=max(dp[i+x+1][j+1],dp[i][j]+a[i+x+1]) （i+x+1<=m&&x>=1）
dp[i+x-1][j-1]=max(dp[i+x-1][j-1],dp[i][j]+a[i+x-1]) （i+x-1<=m&&x>1）
初始化：x=d,dp[d][M]=a[d],其余都为-INF；
Code:
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second #define popcount __builtin_popcount #define popcountll __builtin_popcountll const int N=30010; const int M=300; const int inf=1e9; //const ll INF=1e18; int T,n,m,d,a[N]; int dp[N][800]; bool vis[N][800]; vector<int> v[N]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); // ios::sync_with_stdio(0); // cin.tie(0); n=read(),d=read(); for(int i=1;i<=n;i++) { int x=read(); m=max(m,x); a[x]++; } for(int i=0;i<=m;i++) for(int j=0;j<=700;j++) dp[i][j]=-inf; dp[d][M]=a[d]; for(int i=d;i<=m;i++) for(int j=0;j<=2*M;j++) { int x=j+d-M; if(x<1) continue; if(x-1&&i+x-1<=m) dp[i+x-1][j-1]=max(dp[i+x-1][j-1],dp[i][j]+a[i+x-1]); if(i+x<=m) dp[i+x][j]=max(dp[i+x][j],dp[i][j]+a[i+x]); if(i+x+1<=m) dp[i+x+1][j+1]=max(dp[i+x+1][j+1],dp[i][j]+a[i+x+1]); } int ans=0; for(int i=d;i<=m;i++) for(int j=0;j<=2*M;j++) ans=max(ans,dp[i][j]); printf("%d",ans); return 0; }