HDU

FatMouse and Cheese

题目大意：

给你一个n∗n$n\ast n$的矩阵，每个位置都有一个数字a[i][j],然后从(0,0)开始走，每次只能走1~k步，并且要使得下一个位置的a大于当前位置的a，要求这么走下去的最大和。

数据范围：

多组输入，1≤n≤100$1\le n\le 100$。

解题思路：

对于每个位置，都有情况从其它点过来，或者不可能到当前位置，题目要求的是从(0,0)位置出发，然后数字递增，要是我们从任意位置出发到(0,0)位置，保证数字递减，最后输出dp[0][0]岂不是一样，这样就可以采用dfs，从(0,0)开始，然后所有可以转移过来的位置中取个最大值，那么由于深度搜索，每个位置的最大值都可以求出来，但是仅仅这样是会T的，因为同一位置可能会跑多次，但是每个位置取完最大值之后就不会再次更新为最大的了，假如初始dp为0，那么只要是dp[i][j]不为0的话，它就是最大值了，下次再调用它就不需要重新再继续下去了，最后不断回溯到dp[0][0]位置就是答案了。

AC代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 100;
int n, k, Max;
int a[maxn + 5][maxn + 5];
int dp[maxn + 5][maxn + 5];
int dfs(int x, int y) {
    if(dp[x][y] != 0)return dp[x][y];//记忆化判断，已经有值了就是最大值了，不用再找一遍最大值了
    int Max = 0;
    for(int i = -1; i <= 1; i++)
        for(int j = -1; j <= 1; j++)
            for(int d = 1; d <= k; d++) {//枚举步数
                if(i * j == 0 && i != j) {
                    int dx = x + d * i;
                    int dy = y + d * j;
                    if(dx > n || dy > n || dx < 1 || dy < 1)continue;
                    if(a[dx][dy] > a[x][y]) {
                        Max = max(dfs(dx, dy), Max);//对于所有情况取最大值
                    }
                }
            }
    dp[x][y] = Max + a[x][y];
    return dp[x][y];
}
int main() {
    while(~scanf("%d%d", &n, &k)) {
        bool flag;
        Max = 0;
        if(n == -1 && k == -1)break;
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                scanf("%d", &a[i][j]);
        printf("%d
", dfs(1, 1));//因为我的是从(1,1)点开始的，所以求dp(1,1)最后的值
    }
    return 0;
}