HDU 1078 FatMouse and Cheese​​​​​​​【记忆化搜索】

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

HDU 1078 FatMouse and Cheese

大致意思： 肥鼠把食物储存在n*n的正方形网格，每个网格位置都标上（p,q） 0 <= p < n and 0 <= q < n。每个网格藏有0~100块奶酪。 肥鼠从（0，0）出发，它吃掉所在之处的奶酪，然后水平或竖直（horizontally or vertically）跳跃最多k格之后吃新位置的奶酪。下一位置奶酪必须比当前位置奶酪多。给你n,k,和每个网格里的奶酪数，输出肥鼠不能移动之前能吃的最多奶酪数。   输入： n  k 然后是n*n网格里每处的奶酪数 n=k=-1时结束   输出： 能吃的最多奶酪数

样例:n=3，k=1

1	2	5
10	11	6
12	12	7

 1→2→5→6→11→12=37

补充：n=3，k=2， 1→2→3（跳2格）→4输出10

1	2	3
2	1	1
1	1	4

 

#include<iostream>
#include<string.h>
using namespace std;
const int maxn = 105;
int dp[maxn][maxn],a[maxn][maxn],n,k,ans;
int dir[4][2] = {1,0,-1,0,0,1,0,-1};//右左上下 
int DFS(int x,int y)
{if(dp[x][y]) return dp[x][y];//如果已经赋了值，该值一定是该点最优解，直接返回int ans = 0;for(int j = 1 ; j <= k ; j++)//可以跳跃1～k范围 for(int i = 0 ; i < 4 ;i++)//四个方向 {int newx = x + j * dir[i][0];int newy = y + j * dir[i][1];if(newx >= 0 && newx < n && newy < n && newy >= 0 && a[newx][newy] > a[x][y])ans = max(ans, DFS(newx,newy));  //ans = 能到达现有状态的所有状态中的最大值 }return dp[x][y] = ans + a[x][y];  //这里返回表示已经能确定该点的最优解。
}
int main()
{while(cin>>n>>k){if(n==-1 && k==-1) break;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];//读入每个网格奶酪数 memset(dp,0,sizeof(dp));DFS(0,0);cout<< dp[0][0]<<endl;  //cout<< DFS(0,0) <<endl;}
}

 

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

---