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

题意：给出n*n的格子，每个各自里面有些食物，问一只老鼠每次走最多k步所能吃到的最多的食物

一道简单的记忆化搜索题，从起点开始搜索即可没什么问题，可以拿来练练手。

#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>using namespace std;typedef long long ll;ll dp[110][110];int n , k , map[110][110] , dr[4][2] = {1 , 0 , -1 , 0 , 0 , 1 , 0 , -1};ll dfs(int x , int y) {    if(dp[x][y] != -1) {        return dp[x][y];    }    ll MAX = 0;    for(int i = 1 ; i <= k ; i++) {        for(int j = 0 ; j < 4 ; j++) {            int xx = x + dr[j][0] * i;            int yy = y + dr[j][1] * i;            if(xx >= 0 && yy >= 0 && xx < n && yy < n && map[xx][yy] > map[x][y]) {                ll ans = dfs(xx , yy);                MAX = max(MAX , ans);            }        }    }    dp[x][y] = MAX + map[x][y];    return dp[x][y];}int main() {    while(scanf("%d%d" , &n , &k) != EOF) {        memset(dp , 0 , sizeof(dp));        if(n == -1 && k == -1)            break;        for(int i = 0 ; i < n ; i++) {            for(int j = 0 ; j < n ; j++) {                scanf("%d" , &map[i][j]);            }        }        memset(dp , -1 , sizeof(dp));        ll MAX = dfs(0 , 0);        printf("%lld\n" , MAX);    }    return 0;}

hdu 1078 FatMouse and Cheese（简单记忆化搜索）