| dp-the Treasure Hunter

题目：

思路和实现都不难的动态规划

(._. )

做的时候没看出来长度的限制 担心复杂度太大所以不敢写

(._. )

菜鸡

(._. )

dp[i][j]表示到编号为 i 的岛且上次跳跃长度为 j 时能取到的最多的gems的数目。

注意：岛的编号限制在30000以内，且每次最多增长一步，第一步跳跃长度为d，总的跳跃长度 = d + (d + 1) + (d + 2) + ... + (d + 245)  ≥  1 + 2 + ... + 245 = 245·(245 + 1) / 2  =  30135  >  30000。所以跳跃长度最长为（d+245），最短为（d-245），因此 j 的枚举长度在[d-245，d+245]之间，第二维的空间缩小到500。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<set>

using namespace std;

const int maxn = *1e4+;

int dp[maxn][];;

int num[maxn];

int main()

{

    int base;

    int a, b;

    int n, m, d;

    int i, j, k;

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

    for(i = ; i <= n; i++)

        scanf("%d", &a), num[a]++;

    base = max(d -,);

    memset(dp, -, sizeof dp);

    dp[d][d-base] = num[d];

    int ans=;

    for(i = d ; i <= ; i++)

    {

        for( j =  ;j <= ; j++)

        {

            if(dp[i][j] == -) continue;

            for(k = -; k < ; k++)

            {

                if( j + k < || base + i + j + k > ) continue;

                dp[i + base + j + k][j + k] = max(dp[base + i + j + k][j + k], dp[i][j] + num[i + j + k + base]);

            }

            ans = max(ans, dp[i][j]);

        }

    }

    cout << ans << endl;

    return ;

}