链接：https://ac.nowcoder.com/acm/problem/236173 来源：牛客网

有一片群岛，总共有30001个岛屿，编号从0到30000，其中有 n 个宝藏在这些岛屿中。Kitayuta是一位宝藏猎人，他初始在0号岛屿上。为了获得宝藏，他按照如下规则经过这些岛屿：

  1. ​ 他第一步从 0 号岛屿跨越 d 个岛屿到达 d 号岛屿。
  2. ​ 接下来每一步，他只能前往编号更大的岛屿。并且，假设他前一步跨越了 x 个岛屿，那么他下一步只能跨越 y 个岛屿，其中 y∈{x−1,x,x+1} 且 y>=1 。如果下一步没有可以到达的岛屿，Kitayuta就会停止寻找宝藏。

假设Kitayuta到达有宝藏的岛屿时，他可以获得这个岛屿的所有宝藏。Kitayuta想知道他最多能获得多少宝藏，你能帮帮他吗？

dp

这道题与其想到dp，不如说是递推，一个递归的过程，那么dp就是优化递归过程，对于每一个位置都有三种选择，-1，0，1，那么我们要记录的还有就是走到当前岛屿i是用了几步，这个用数组维护即可，所以一开始初始化一定要写，不写就是70%，之后递推即可。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define int long long
/*inline __int128 read(){
    __int128 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 * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}*/
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
//用__int128时记得删掉关流
int f[500010];
std::map<int,int> mp;
int stp[500010];
int dd[]={-1,0,1};
void slove()
{
   int n,d;
   std::cin>>n>>d;
   for(int i=1;i<=n;i++)
   {
   		int x;
   		std::cin>>x;
   		mp[x]++;
   }
   memset(f,-0x3f,sizeof(f));//还没跳到的位置
   f[d]=mp[d];
   stp[d]=d;
   int ans=0;
   for(int i=d;i<=30000;i++)
   {
   		if(!stp[i]) continue;//walked pass
   		 ans=std::max(ans,f[i]);
   		for(int j=0;j<3;j++)
   		{
   			int p=std::max(1LL,stp[i]+dd[j]);
   			if(i+p>30001||i+p<0) break;
   			if(f[i+p]<f[i]+mp[i+p])
   			{
                //std::cout<<"in"<<endl;
   				f[i+p]=f[i]+mp[i+p];
                stp[i+p]=p;
			}
			   
		}
   }
   std::cout<<ans<<endl;
}
signed main()
{
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}

DFS

搜索应该是最好想到的，因为一共就那么几种情况，但这道题的状态也不少，直接递归肯定不太行，还是要去剪枝，思路就是超过岛屿总数或者宝藏最大位置的剪掉，最关键的剪枝就是判断走过的路，如果这个岛屿之前走过，并且你现在走到这个岛屿时拿到的宝藏没有上次多，这个状态就是不必要的，可以剪掉，然后就是开心的搜索了。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
/*inline __int128 read(){
    __int128 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 * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}*/
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
//用__int128时记得删掉关流
std::map<int, int> mp;
int ans=0,maxpos=0;
int f[300010];//走到这个位置的最大值
void dfs(int last,int cur,int val)
{
    if(cur>maxpos) return ;
    if(cur>30001) return ;
    val+=mp[cur];
    if(val<f[cur]) return ;
    ans=std::max(ans,val);
    f[cur]=std::max(f[cur],val);
    if(last-1>0) dfs(last-1,cur+last-1,val);
    dfs(last,cur+last,val);
    dfs(last+1,cur+last+1,val);

}
void slove()
{
    int n,d;
    std::cin>>n>>d;
    for(int i=1;i<=n;i++) 
    {
        int x;
        std::cin>>x;
        mp[x]++;
        maxpos=std::max(maxpos,x);
    }
    dfs(d,d,0);
    std::cout<<ans<<endl;


}
int main()
{
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}