随手练——HDU 1078 FatMouse and Cheese(记忆化搜索)

http://acm.hdu.edu.cn/showproblem.php?pid=1078

题意:

一张n*n的格子表格,每个格子里有个数,每次能够水平或竖直走k个格子,允许上下左右走,每次走的格子上的数必须比上一个走的格子的数大,问最大的路径和。

记忆化搜索

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

][] = { {, },{ -, }, {, }, {, -} };
][];
][];
int n, k;
int dfs(int x,int y) {
    ;
    if (!dp[x][y]) {
        ; i <= k; i++) {
            ; j < ; j++) {
                ], toy = y + i * dir[j][];
                 && tox <= n -  && toy >=  && toy <= n - ) {
                    if (m[tox][toy] > m[x][y]) {
                        int t = dfs(tox, toy);
                        max = t > max ? t : max;
                    }
                }
            }
        }
        dp[x][y] = max + m[x][y];
    }
    return dp[x][y];
}
int main() {
     || k != -)){
        memset(dp, , sizeof(dp));
        ; i < n; i++) {
            ; j < n; j++) {
                scanf("%d", &m[i][j]);
            }
        }
        cout << dfs(, ) << endl;
    }
    ;
}
上一篇:go中的数据结构字典-map


下一篇:『GoLang』字典Map