8636 跳格子(dfs+记忆化搜索)

8636 跳格子

该题有题解

时间限制:2457MS  内存限制:1000K
提交次数:139 通过次数:46

题型: 编程题   语言: G++;GCC

Description

    地上有一个n*m 的数字格子,每个格子有一个坐标(i,j)(其中1<=i<=n , 1<=j<=m),规定左上角为(0,0),
右下角为(n,m),你要从最左端的一列的任意位置开始跳到最右边格子外。
下面两条你跳的时候的约束规则:
一、因为你的力气有限,每次只能跳一定的距离。给定一个k 为你的弹跳力,则从(i1,j1)起跳,你能跳到
任意(i2,j2)且符合k>=(i1-i2)*(i1-i2)+( j1-j2)*( j1-j2)。
二、每次你至少要向右走一格,也就是说你不能跳到同一列的格子上戒者往回跳。再换句话说就是依次跳
到的位置的坐标中,j 必须是递增的。
每个格子里边有一个分值,当你跳到那里就可以获取到该格子的分数。
现在请你求出你最多能得多少分?
现在假设有一个5×6 的格子,你的弹跳能力为4,则如图所示你能得到17 分。

8636 跳格子(dfs+记忆化搜索)

跳跃路径为(4,1)->(3,2)->(3,4)->(4,5)->(4,6)->跳出格子。

输入格式

第一行包含一个整数T,表示T 个case。
每个case 第一行包含n m k 三个整数(1<=n,m,k<=100)
接下来n行,每行m个分值,格子里的分数的绝对值小于20000

输出格式

输出最大得分。

输入样例

1
5 6 4
1 2 -1 2 1 1
2 3 -1 2 3 1
3 4 -1 2 2 3
4 2 -1 1 3 4
3 1 -1 1 1 4

输出样例

17

题解

记忆化搜索。每次从第i行第一个开始深搜,记录下搜过的点,下次如果再次搜到这个点就直接返回这个点的值就行了。
(ps:这题很多细节要注意,尽量少点一些没必要的判断,不然很容易超时)

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,k;
int map[][];
int dp[][];
int DFS(int l,int r)
{
int maxn=-;
if (r==m) return map[l][r];
if (dp[l][r]) return dp[l][r];
for (int i=; i<=n; ++i)
for (int j=r+; j<=m; ++j)
if ((i-l)*(i-l)+(j-r)*(j-r)<= k)
maxn=max(maxn,DFS(i,j));
dp[l][r]=maxn+map[l][r];
return dp[l][r];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
memset(dp,,sizeof(dp));
for (int i=; i<=n; ++i)
for (int j=; j<=m; ++j)
scanf("%d",&map[i][j]);
int maxn=-;
for (int i=; i<=n; ++i)
maxn=max(maxn,DFS(i,));
printf("%d\n",maxn);
}
return ;
}
上一篇:dfs+记忆化搜索,求任意两点之间的最长路径


下一篇:hdu 1078 FatMouse and Cheese (dfs+记忆化搜索)