Codeforces Round #286 Div.1 A Mr. Kitayuta, the Treasure Hunter –DP

题意：0~30000有30001个地方，每个地方有一个或多个金币，第一步走到了d，步长为d，以后走的步长可以是上次步长+1,-1或不变，走到某个地方可以收集那个地方的财富，现在问走出去(>30000)之前最多可以收集到多少财富。

解法：容易想到DP，dp[i][j]表示到达 i 处，现在步长为 j 时最多收集到的财富，转移也不难,cnt[i]表示 i 处的财富。

dp[i+step-1] = max(dp[i+step-1],dp[i][j]+cnt[i+step+1])

dp[i+step] = max(dp[i+step],dp[i][j]+cnt[i+step])

dp[i+step+1] = max(dp[i+step+1],dp[i][j]+cnt[i+step+1])

但是步长直接开30000存的话肯定是不行的，又发现，其实走过30000之前，步长的变化不会很大，如果步长每次增加1的话，那么最少1+2+…+n=n(n+1)/2 > 30000, n<250，即步长变化不会超过250.所以第二维保存相对原始步长的改变量，-250~250，开500就够了，这样就不会MLE了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 10007int dp[*N][];
int cnt[*N],ans;int main()
{
    int i,j,n,d;
    while(scanf("%d%d",&n,&d)!=EOF)
    {
        memset(cnt,,sizeof(cnt));
        for(i=;i<=n;i++)
        {
            scanf("%d",&j);
            cnt[j]++;
        }
        memset(dp,-,sizeof(dp));
        dp[d][] = cnt[d];
        ans = dp[d][];
        for(i=d;i<=;i++) {
            for(j=;j<=;j++) {
                if(dp[i][j] == -) continue;
                int to = i+d+j-;
                if(to <= ) {
                    dp[to][j] = max(dp[to][j],dp[i][j]+cnt[to]);
                    ans = max(ans,dp[to][j]);
                }
                if(to+ <= ) {
                    dp[to+][j+] = max(dp[to+][j+],dp[i][j]+cnt[to+]);
                    ans = max(ans,dp[to+][j+]);
                }
                if(to <=  && to-i > ) {
                    dp[to-][j-] = max(dp[to-][j-],dp[i][j]+cnt[to-]);
                    ans = max(ans,dp[to-][j-]);
                }
            }
        }
        cout<<ans<<endl;
    }
    return ;
}