505C Mr. Kitayuta, the Treasure Hunter

传送门

题目大意

一共有30000个位置，从第0个位置开始走，第一次走k步，对于每一次走步，可以走上一次的k+1 ，k ，k-1步数（必须大于等于1），每个岛上有value，求最大能得到的value能有多少。

分析

首先我们不难想到dpij表示走到第i个位置，上次走的步数为j，然而30000*30000时间复杂度和空间复杂度都会爆炸，所以我们考虑如何优化掉一维，然而我们发现是无法优化掉一维的。

但由于一个只有30000个位置，所有我们想到上次走的步数的所有可能情况可能不是很多，由式子d+(d+1)+(d+2)+…+(d+maxl)≤30000可得maxl大致是250，也就是说上次走的步数最少是d-250，最多是d+250.于是我们得到dpij，其中i表示考虑到第i个位置，j表示上次走的长度-d，注意为了防止数组出现负数我们将第二维统一加上maxl。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define sp cout<<"---------------------------------------------------"<<endl;

const int inf=1e9+;

int dp[][],maxl=,cnt[],N=;

int main(){

      int n,m,i,j,k,d;

      scanf("%d%d",&n,&d);

      for(i=;i<=n;i++)scanf("%d",&m),cnt[m]++;

      for(i=;i<=N;i++)for(j=;j<=;j++)dp[i][j]=-inf;

      dp[d][maxl]=cnt[d]+cnt[];

      for(i=d;i<N;i++)for(j=-maxl;j<=maxl;j++)if(dp[i][j+maxl]!=-inf){

        if(i+j+d<=N&&j+d>)

          dp[i+j+d][j+maxl]=max(dp[i+j+d][j+maxl],dp[i][j+maxl]+cnt[i+j+d]);

        if(j+d->&&i+j+d-<=N&&j->=-maxl)

          dp[i+j+d-][j-+maxl]=max(dp[i+j+d-][j-+maxl],dp[i][j+maxl]+cnt[i+j+d-]);

        if(j+d+>&&i+j+d+<=N&&j+<=maxl)

          dp[i+j+d+][j++maxl]=max(dp[i+j+d+][j++maxl],dp[i][j+maxl]+cnt[i+j+d+]);

      }

      int ans=;

      for(i=;i<=N;i++)for(j=-maxl;j<=maxl;j++)ans=max(ans,dp[i][j+maxl]);

      cout<<ans<<endl;

      return ;

}