HDU-1078-FatMouse and Cheese

这题就是记忆化搜索，其实很像数位dp的写法。
这题首先，看一眼，甚至看好几眼都看不出边界在哪，让人有点摸不着头脑。
所以我们直接开一个dp数组，让dp数组反向更新一个最大值，然后上层的递归直接使用就可以了。
这时候边界条件就很明显了，sum = max(sum, dfs(dx, dy)); 也就是说这一个点之后的最大值，应该和下一个点的最大值进行比较更新。
最后我们更新dp数组，让它加上这一个点的值，就是这个点的最大值了。

#include <cstdio>
#include <cstring>
int map[105][105], dp[105][105];
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, k, ans;

int max(int x,int y)
{
    return x > y ? x : y;
}

int dfs(int x,int y)
{
    if (dp[x][y])
        return dp[x][y];
    int sum = 0;
    for (int i = 0; i < 4;i++) {
        for (int j = 1; j <= k;j++) {
            int dx = x + j * d[i][0];
            int dy = y + j * d[i][1];
            if (dx>=0&&dy>=0&&dx<n&&dy<n)
                if (map[dx][dy]>map[x][y])
                    sum = max(sum, dfs(dx, dy));
        }
    }
    return dp[x][y] = sum + map[x][y];
}

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