daily 1

CF 505C

开始想到直接dp，但是会爆内存，所以我们用对应跳的偏移量来存我们的第二维就好啦，注意偏移量可以是负数，所以要往右边移250

void solve(){
  int n,d;
  cin>>n>>d;
  vector<int>a(N);
  for(int i=0;i<n;++i){
    int x;
    cin>>x;
    a[x]++;
  }
  vector dp(N,vector<ll>(2*LIM+2,-1e8));
  dp[d][LIM]=a[d];
  ll ans=-1;
  for(int i=1;i<N;++i){
    for(int j=0;j<=2*LIM;++j){
        int last_pos=i-(j+d)+250;
        if(last_pos<0||last_pos>=i)continue;
        for(int k=-1;k<=1;++k){
            if(j+k>0){
                dp[i][j]=max(dp[last_pos][j+k]+a[i],dp[i][j]);
            }
        }
        ans=max(ans,dp[i][j]);
    }
  }
  cout<<ans<<'\n';
  return;
}