题目大意：

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

数据范围：

多组输入，1≤n≤1001≤n≤100。

解题思路：

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

AC代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         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\n", dfs(1, 1));//因为我的是从(1,1)点开始的，所以求dp(1,1)最后的值    }    return 0;}