【题目链接】:

【题意】

一开始你跳一步长度为d;

之后你每步能跳d-1,d,d+1这3种步数;

然后在路上有很多个位置有treasure;

问你,你最多能获得多少个treasure;

最远跳到30000

【题解】

记忆化搜索;

设dp[x][y]表示跳到第x个位置了;

然后前一步跳的步数为d+y能够获得的最多treasure个数;

这里y能够为负值;且d+y>0;

这里用和d的差值作为第二维是因为;

1+2+3…+n=(1+n)*n/2

然后令其等于30000的话;

可以发现,最大的差值应为250左右,不可能更大了;

因为即使每一步都是递增的,然后d=0,也能够满足在差值为250就跳出边界;

因此用差值来作为第二维是正确的选择>_<

然后因为差值能为负值;

所以在写的时候,第二维加个偏移量就好;

【Number Of WA】

1

【完整代码】

#include 
     
      using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define ms(x,y) memset(x,y,sizeof x)#define Open() freopen("F:\\rush.txt","r",stdin)#define Close() ios::sync_with_stdio(0),cin.tie(0)typedef pair
      
        pii;typedef pair
       
         pll;const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };const double pi = acos(-1.0);const int N = 3e4+100;const int py = 250;int n, d,num[N];int f[N][600];int dfs(int x, int l){    //cout << x << ' '<
        
         << endl;    if (x > 30000) return 0;    if (f[x][l+py] != -1)        return f[x][l+py];    int temp = 0;    rep1(i, -1, 1)    {        if (d + l + i <= 0) continue;        int y = x + d + l + i;        temp = max(temp, num[x] + dfs(y, l + i));    }    return f[x][l+py] = temp;}int main(){    //Open();    Close();//scanf,puts,printf not use            //init??????    ms(f, -1);    cin >> n >> d;    rep1(i, 1, n)    {        int x;        cin >> x;        num[x]++;    }    cout << dfs(d, 0) << endl;    return 0;}