题目链接：http://codeforces.com/problemset/problem/505/C
题意：
有n个宝石，分别在位置p[i]。(1 <= n,p[i] <= 30000)
初始时你在位置0，第一次走可以往前跳d的距离。
从第二次跳开始，如果前一次跳的距离是x，这一次跳的距离只能是x-1,x,x+1中的一种。
没每跳到一个地方，会获得那里的所有宝石。
问你最多能拿到多少宝石。
题解：
表示状态：
dp[i][j] = max gems
表示初始在位置i，上一次跳的距离为j，在这以及之后所能拿到的最大价值。
找出答案：
ans = dp[d][d]
如何转移：
dp[i][j] = max dp[i+j-1][j-1]
dp[i][j] = max dp[i+j][j]
dp[i][j] = max dp[i+j+1][j+1]
然而O(N^2)过不了……
因为每次跳的距离最多变化1，所以当n=30000时，跳的距离变化小于250，需要用到的j∈[d-250, d+250]。
精确一些就是j∈[d-k, d+k]，其中k = ((sqrt(8n+1)-1)/2)+5。
将所有j映射到[0, 2k]的范围内，这样时间和空间就都能满足了。
边界条件：
if(i>maxd) dp[i][j] = 0
maxd是有宝石的最远距离。
当i>maxd时，之后不可能有任何收获。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 30005
#define MAX_V 1005
#define cal(x) ((x)-d+k) using namespace std; int n,d,k;
int maxd=;
int a[MAX_N];
int dp[MAX_N][MAX_V]; int dfs(int i,int j)
{
if(i>maxd) return ;
if(dp[i][cal(j)]!=-) return dp[i][cal(j)];
if(j->) dp[i][cal(j)]=max(dp[i][cal(j)],dfs(i+j-,j-)+a[i]);
dp[i][cal(j)]=max(dp[i][cal(j)],dfs(i+j,j)+a[i]);
dp[i][cal(j)]=max(dp[i][cal(j)],dfs(i+j+,j+)+a[i]);
return dp[i][cal(j)];
} int main()
{
cin>>n>>d;
memset(a,,sizeof(a));
int x;
for(int i=;i<=n;i++)
{
cin>>x;
a[x]++;
maxd=max(maxd,x);
}
k=(int)((sqrt(n*+)-1.0)/2.0)+;
memset(dp,-,sizeof(dp));
cout<<dfs(d,d)<<endl;
}