FatMouse and Cheese---hdu1078（记忆化搜索=搜索+dp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1078

题意就是有n*n的地图，每个地方都有食物，数量不同，老鼠在（0，0）的位置每次它最多跳 k 步，每次吃只能吃比当前位置食物多的食物，求最大值；

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 110
#define INF 0xffffff

int n, k, dp[N][N], a[N][N];
int dir[4][2]= {{1,0},{-1,0},{0,-1},{0,1} };

int DFS(int x, int y)
{
    int Max=0, sum;
    if(dp[x][y]==-1)
    {
        for(int i=1; i<=k; i++)
        {
            for(int j=0; j<4; j++)
            {
                int xx=x+dir[j][0]*i;
                int yy=y+dir[j][1]*i;
                if(xx<n&&xx>=0 && yy<n&&yy>=0 && a[xx][yy]>a[x][y])
                {
                    sum=DFS(xx, yy);
                    Max=max(Max, sum);
                }
            }
        }
        dp[x][y]=Max+a[x][y];
    }
    return dp[x][y];
}

int main()
{
    ///freopen("In.txt", "r", stdin);

    while(scanf("%d%d", &n, &k), n!=-1||k!=-1)
    {
        memset(a, 0, sizeof(a));
        memset(dp, -1, sizeof(dp));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                scanf("%d",&a[i][j]);
        int ans = DFS(0,0);
        printf("%d
", ans);
    }
    return 0;
}