Codeforces Round #286 (Div. 二) C题 Mr. Kitayuta, the Treasure Hunter （DFS+记忆化DP）

Codeforces Round #286 (Div. 2) C题 Mr. Kitayuta, the Treasure Hunter （DFS+记忆化DP）

题目地址：http://codeforces.com/contest/505/problem/C

从d点开始，每个点都有三个方向，形成了一棵树，那么就从跟结点开始进行dfs查找，dp数组记录当前的点和长度，当这两个条件相同的时候，显然，后面的子树是完全相同的，于是用记忆化来优化。

代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=100000000;
const int INF=0x3f3f3f3f;
const double eqs=1e-8;

int dp[31000][300], w[31000], max1, max2;
int dfs(int cur, int lenth)
{
        if(cur>max1) return 0;
        if(dp[cur][lenth]!=-1) return dp[cur][lenth];
        if(lenth>1) dp[cur][lenth]=max(dp[cur][lenth],dfs(cur+lenth-1,lenth-1)+w[cur]);
        dp[cur][lenth]=max(dp[cur][lenth],dfs(cur+lenth,lenth)+w[cur]);
        dp[cur][lenth]=max(dp[cur][lenth],dfs(cur+lenth+1,lenth+1)+w[cur]);
        max2=max(max2,dp[cur][lenth]);
        return dp[cur][lenth];
}
int main()
{
        int n, d, i, j, x, len, pre;
        max1=-1;
        scanf("%d%d",&n,&d);
        memset(w,0,sizeof(w));
        memset(dp,-1,sizeof(dp));
        for(i=0; i<n; i++) {
                scanf("%d",&x);
                w[x]++;
                max1=max(max1,x);
        }
        max2=0;
        dfs(d,d);
        printf("%d\n",max2);
        return 0;
}