正文

hdu1078记忆化搜索

LuZhiyuan  LuZhiyuan  2022-08-24  207

关键词：

FatMouse and Cheese

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9499 Accepted Submission(s): 4007

Problem Description

FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he‘s going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse -- after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.

Input

There are several test cases. Each test case consists of

a line containing two integers between 1 and 100: n and k
n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) ... (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), ... (1,n-1), and so on.
The input ends with a pair of -1‘s.

Output

For each test case output in a line the single integer giving the number of blocks of cheese collected.

Sample Input

3 1

1 2 5

10 11 6

12 12 7

-1 -1

Sample Output

Source

Zhejiang University Training Contest 2001

题意：

n*n的矩阵，从左上角开始，每次最多只能走k步，并且只能走到权值更大的点，问走过的所有的点的最大权值和是多少。

代码：

//普通的搜索会超时，记忆化搜索，当搜到某点的权值和在前面的搜索中已经算过了就直接返回。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x7fffffff;
int f[103][103],mp[103][103];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,k;
int dfs(int x,int y)
{
    if(!f[x][y]){
        int tmp=0;
        for(int j=1;j<=k;j++){
            for(int i=0;i<4;i++){
                int xx=x+dir[i][0]*j,yy=y+dir[i][1]*j;
                if(xx<0||xx>=n||yy<0||yy>=n) continue;
                if(mp[xx][yy]<=mp[x][y]) continue;
                tmp=max(tmp,dfs(xx,yy));
            }
        }
        f[x][y]=tmp+mp[x][y];
    }
    return f[x][y];
}
int main()
{
    while(scanf("%d%d",&n,&k)){
        if(n==-1&&k==-1) break;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&mp[i][j]);
            }
        }
        memset(f,0,sizeof(f));
        int ans=dfs(0,0); 
        printf("%d
",ans);
    }
    return 0;
}

hdu1078fatmouseandcheese（记忆化搜索）

FatMouseandCheeseTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):8610 AcceptedSubmission(s):3611 ProblemDescrip 查看详情

hdu1078fatmouseandcheese（记忆化搜索）

...这些点到达当前点所能获得的cheese的最大值。思路：记忆化搜索。假设对于当前的点。没有被搜索过（dp[i][j]=0）。那么就对其进行搜索。搜索过程中查看详情

hdu1078fatmouseandcheese（简单记忆化搜索）

...只老鼠每次走最多k步所能吃到的最多的食物一道简单的记忆化搜索题，从起点开始搜索即可没什么问题，可以拿来练练手。 #include<iostream>#include<cstring>#include< 查看详情

hdu1078fatmouseandcheese（记忆化搜索）(代码片段)

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1078FatMouseandCheeseTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):13356 &n 查看详情

hdu1078fatmouseandcheese简单记忆化搜索

...下子走k不。问小明能拿到多少奶酪吃？解题思路：简单记忆化搜索一下就行。访问到一个网格，如果该网格已经搜过，就直接返回记录的值。代码：1constint 查看详情

hdu1078fatmouseandcheese(记忆化搜索)

...格子要大于前一个，问最大和是多少。析：一个很简单的记忆搜索，dp[i][j]，表示到达（i，j）的最大和是多少，我们可以反着推出答案。代码如下：#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<cstdio>#in 查看详情

hdu1078fatmouseandcheese(记忆化搜索dp)

...次只能水平或垂直走，问最多能得到的奶酪。解题思路：记忆化搜索，这方面还是写的太少，还要看别人才会，这个就当个例子参考吧。1#include 查看详情

hdu-1078-fatmouseandcheese(记忆化搜索)(代码片段)

链接:https://vjudge.net/problem/HDU-1078#author=0题意:FatMousehasstoredsomecheeseinacity.Thecitycanbeconsideredasasquaregridofdimensionn:eachgridlocationislabelled(p,q)where0<=p<nand0<=q<n.AteachgridlocationFatmousehashidbetween0and100blocksofcheeseinahole.Nowhe‘sgoingtoenjoyhisfav... 查看详情

hdu1078记忆化搜索

题意：给你n*n的地图每一个格子有一个值仅仅能从值小的格子走到值较大的格子给你k每次上下左右最多走k步问你走的格子最大值的是多少dp【i】【j】表示以（i，j）为起点的能得到的最大值然后深搜... 查看详情

hdu1078fatmouseandcheese记忆化搜索(代码片段)

...索做，但是在搜索的过程中，我们应该加入dp的思想，即记忆化搜索，对于已经搜索过的点，我们就可以不用重复搜索了，直接调用它的值就行。# 查看详情

hdu1078fatmouseandcheese

记忆化搜索，$dp$。每一个点走到的最长距离是固定的，也就是只会算一次，那么记忆化一下即可，也可以按值从小到大排序之后进行$dp$。记忆化搜索：#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;intT,n,k;int... 查看详情

hdu1078zoj1107fatmouseandcheese记忆化搜索(代码片段)

FatMouseandCheeseTimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):15207AcceptedSubmission(s):6443ProblemDescriptionFatMousehasstoredsomecheeseinacity.Thecitycanbeconsideredasasquaregridofdimensionn:eachgridlocationislabelled(p,q)where0<=p<nand0<=q<... 查看详情

hdu-1078fatmouseandcheese（记忆化+dfs）(代码片段)

FatMouseandCheese FatMousehasstoredsomecheeseinacity.Thecitycanbeconsideredasasquaregridofdimensionn:eachgridlocationislabelled(p,q)where0<=p<nand0<=q<n.AteachgridlocationFatmousehash 查看详情

记忆化搜索hdu1331

FunctionRunFunTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):2586 AcceptedSubmission(s):1255ProblemDescription 查看详情

hdu1978记忆化搜索

HowmanywaysTimeLimit:3000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):5203 AcceptedSubmission(s):3067ProblemDescription这是一查看详情

hdu1176免费馅饼（记忆化搜索）

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1176题意不解释了简单的记忆化搜索可以拿来练练手，注意要从pos=5开始搜索#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cma 查看详情

hdu2452navymaneuvers记忆化搜索

这题目意思能忍？读了半年，乱七八糟的记忆化搜索拖拖的，dp[i][0]代表以获得最小值为目标的船以i为起点。dp[i][1]代表以获得最大值为目标的船以i为起点。接下来暴力枚举入度为0的点为起点，開始记忆化搜索，constintN=... 查看详情

hdu3779railroad（记忆化搜索）

RailroadTimeLimit:4000/2000ms(Java/Other) MemoryLimit:32768/32768K(Java/Other)TotalSubmission(s):10 AcceptedSubmission(s):3Font: TimesNewRoman | Verdan 查看详情