FatMouse and Cheese HDU - 1078 （记忆化搜索 DP）

本文主要是介绍FatMouse and Cheese HDU - 1078 （记忆化搜索 DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

FatMouse and Cheese

题目链接：HDU - 1078

题意：一个n*n的迷宫， 一只老鼠每次只能横着走或竖着走， 且最多走k布停下， 且每次停下的地点的值上一次地点的值大；

问最多得到的价值；

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
int n, k;
int maze[105][105];
int dp[105][105];
int nex[4][2]={1, 0, 0, 1, -1, 0, 0, -1};
int dfs(int x, int y){int tx, ty;int ans=0;if(!dp[x][y]){for(int i=1; i<=k; i++){for(int j=0; j<4; j++){tx=x+nex[j][0]*i;ty=y+nex[j][1]*i;if(tx>n||ty>n||ty<1||tx<1) continue;if(maze[tx][ty]>maze[x][y]) ans=max(ans, dfs(tx, ty));}}dp[x][y]=ans+maze[x][y];}return dp[x][y];
}
int main(){while(~scanf("%d%d", &n, &k)){if(n==-1&&k==-1) break;for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){scanf("%d", &maze[i][j]);}}memset(dp, 0, sizeof(dp));int ans=dfs(1, 1);cout << ans << endl;}return 0;
}

这篇关于FatMouse and Cheese HDU - 1078 （记忆化搜索 DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---