Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >hdu1078 zoj1107(记忆化搜索/DP)

hdu1078 zoj1107(记忆化搜索/DP)

作者头像
全栈程序员站长
发布于 2022-09-17 02:28:36
发布于 2022-09-17 02:28:36
18400
代码可运行
举报
运行总次数:0
代码可运行

大家好,又见面了,我是你们的朋友全栈君。

题目链接:zoj hdu

题目大意:老鼠从(0,0)出发,每次在同一个方向上最多前进k步,且每次到达的位置上的数字都要比上一个位置上的数字大,求老鼠经过的位置上的数字的和的最大值

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
int n;
int k;//前进的步数
int map[105][105];
int ans[105][105];//记忆化搜索,保存中间搜索结果
int search(int x,int y)
{
    int dx,dy;//要去的下一个位置
    int i,maxx = 0;
    if(ans[x][y] != -1) return ans[x][y];//已经搜索过,直接返回结果
    for(i = 1 ; i <= k ; i ++)//向前走的步数
    {
        dx = x - i;//向上
        if(dx >= 0 && dx < n && map[dx][y] > map[x][y])
        {
            ans[dx][y] = search(dx,y);
            maxx = max(maxx,ans[dx][y]);
        }
        dx = x + i;//向下
        if(dx >= 0 && dx < n && map[dx][y] > map[x][y])
        {
            ans[dx][y] = search(dx,y);
            maxx = max(maxx,ans[dx][y]);
        }
        dy = y - i;//向左
        if(dy >= 0 && dy < n && map[x][dy] > map[x][y])
        {
            ans[x][dy] = search(x,dy);
            maxx = max(maxx,ans[x][dy]);
        }
        dy = y + i;//向右
        if(dy >= 0 && dy < n && map[x][dy] > map[x][y])
        {
            ans[x][dy] = search(x,dy);
            maxx = max(maxx,ans[x][dy]);
        }
    }
    return maxx + map[x][y];
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&k) && (n != -1 && k != -1))
    {
        for(i = 0 ; i < n ; i ++)
         for(j = 0 ; j < n ; j ++)
          scanf("%d",&map[i][j]);
        memset(ans,-1,sizeof(ans));
        printf("%d\n",search(0,0));
    }
    return 0;
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/164454.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
记忆化搜索专题
大家好,又见面了,我是你们的朋友全栈君。   什么是记忆化搜索呢?搜索的低效在于没有能够很好地处理重叠子问题;动态规划虽然比较好地处理了重叠子问题,但是在有些拓扑关系比较复杂的题目面前,又显得无奈。记忆化搜索正是在这样的情况下产生的,它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起,扬长避短,简单实用,在信息学中有着重要的作用。   用一个公式简单地说:记忆化搜索=搜索的形式+动态规划的思想。   动态规划:就是一个最优化问题,先将问题分解为子问题,并且对于这些分解的子问题自身就是最优的才能在这个基础上得出我们要解决的问题的最优方案,要不然的话就能找到一个更优的解来替代这个解,得出新的最优自问题,这当然是和前提是矛盾的。动态规划不同于 贪心算法,因为贪心算法是从局部最优来解决问题,而动态规划是全局最优的。用动态规划的时候不可能在子问题还没有得到最优解的情况下就做出决策,而是必须等待子问题得到了最优解之后才对当下的情况做出决策,所以往往动态规划都可以用 一个或多个递归式来描述。而贪心算法却是先做出一个决策,然后在去解决子问题。这就是贪心和动态规划的不同。 一般遇到一个动态规划类型的问题,都先要确定最优子结构,还有重叠子问题,这两个是动态规划最大的特征,然后就是要写 动态规划的状态方程,这个步骤十分十分的重要的,写动归方程是需要一定的经验的,这可以通过训练来达到目的。接着就是要自底向上的求解问题的,先将最小规模的子问题的最优解求出,一般都用一张表来记录下求得的解,到后来遇到同样的子问题的时候就可以直接查表得到答案,最后就是通过一步一步的迭代得出最后问题的答案了。 我的理解最重要的东西就是一定会要一个数组或者其他的存储结构存储得到的子问题的解。这样就可以省很多时间,也就是典型的空间换时间 动态规划的一种变形就是记忆化搜索,就是根据动归方程写出递归式,然后在函数的开头直接返回以前计算过的结果,当然这样做也需要一个存储结构记下前面计算过的结果,所以又称为记忆化搜索。 记忆化搜索递归式动态规划 1.记忆化搜索的思想 记忆化搜索的思想是,在搜索过程中,会有很多重复计算,如果我们能记录一些状态的答案,就可以减少重复搜索量 2、记忆化搜索的适用范围 根据记忆化搜索的思想,它是解决重复计算,而不是重复生成,也就是说,这些搜索必须是在搜索扩展路径的过程中分步计算的题目,也就是“搜索答案与路径相关”的题目,而不能是搜索一个路径之后才能进行计算的题目,必须要分步计算,并且搜索过程中,一个搜索结果必须可以建立在同类型问题的结果上,也就是类似于动态规划解决的那种。 也就是说,他的问题表达,不是单纯生成一个走步方案,而是生成一个走步方案的代价等,而且每走一步,在搜索树/图中生成一个新状态,都可以精确计算出到此为止的费用,也就是,可以分步计算,这样才可以套用已经得到的答案 3、记忆化搜索的核心实现 a. 首先,要通过一个表记录已经存储下的搜索结果,一般用哈希表实现 b.状态表示,由于是要用哈希表实现,所以状态最好可以用数字表示,常用的方法是把一个状态连写成一个p进制数字,然后把这个数字对应的十进制数字作为状态 c.在每一状态搜索的开始,高效的使用哈希表搜索这个状态是否出现过,如果已经做过,直接调用答案,回溯 d.如果没有,则按正常方法搜索 4、记忆化搜索是类似于动态规划的,不同的是,它是倒做的“递归式动态规划”。
全栈程序员站长
2022/09/19
7420
记忆化搜索专题
POJ1088 滑雪题解+HDU 1078(记忆化搜索DP)
Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5
风骨散人Chiam
2020/10/28
6780
【算法专题】记忆化搜索
什么是记忆化搜索呢?记忆化搜索其实就是带了"备忘录"的递归,给递归加上一个"备忘录",递归每次返回的时候,将结果放到"备忘录"里面,在每次进入递归的时候,往"备忘录"里面看看,当前需要递归的数据时候在"备忘录"里存在,如果存在,那么就可以直接取此次的结果,不用进行这次的递归。
YoungMLet
2024/03/01
2710
【算法专题】记忆化搜索
hdu 1078 FatMouse and Cheese (dfs+记忆化搜索)
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4811 Accepted Submission(s): 1945 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
全栈程序员站长
2022/07/10
2200
论记忆化搜索
什么是记忆化搜索呢?搜索的低效在于没有能够很好地处理重叠子问题;动态规划虽然比较好地处理了重叠子问题,但是在有些拓扑关系比较复杂的题目面前,又显得无奈。记忆化搜索正是在这样的情况下产生的,它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起,扬长避短,简单实用,在信息学中有着重要的作用。用一个公式简单地说:记忆化搜索=搜索的形式+动态规划的思想。
全栈程序员站长
2022/09/17
3540
POJ-1088 滑雪 (记忆化搜索,dp)
滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 Accepted: 32289 Description Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2
ShenduCC
2018/04/25
1.1K0
DFS:记忆化搜索
小陈在拼命
2024/04/10
1450
DFS:记忆化搜索
poj 1088 记忆化搜索||动态规划
记忆化搜索也也是采用递归深搜的对数据进行搜索,但不同于直接深搜的方式,记忆化搜索是在每次搜索时将得到的结果保存下来,避免了重复计算,这就是所谓的记忆化。记忆化应该是属于动态规划。
xindoo
2021/01/22
3680
记忆化搜索系列一>矩阵中的最长递增路径
用户11305962
2025/03/12
1260
记忆化搜索系列一>矩阵中的最长递增路径
POJ 3176-Cow Bowling(DP||记忆化搜索)
The cows don’t use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this:
全栈程序员站长
2022/07/05
2290
【算法/学习】:记忆化搜索
记忆化搜索(Memoization Search):是一种通过存储已经遍历过的状态信息,从而避免对同一状态重复遍历的搜索算法。
IsLand1314
2024/10/15
2130
【算法/学习】:记忆化搜索
记忆化搜索算法
记忆化搜索算法事实上是一种对递归算法的优化 因为在递归算法中有很多重复计算,导致了非常离谱的时间和空间复杂度 所以我们采用记住计算结果的方式,能很大程度上减少复杂度
全栈程序员站长
2022/09/17
4650
啥是记忆化搜索?
有一天小K去滑雪,雪山高低不平,当然小K只能从高的地方向低的地方滑,那如何选择路线才能滑的最远呢?
小K算法
2022/04/18
3780
啥是记忆化搜索?
hdoj 1078 FatMouse and Cheese(记忆化搜索)
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.
xindoo
2021/01/22
3140
HDU ACM 1078 FatMouse and Cheese 记忆化+DFS[通俗易懂]
题意:FatMouse在一个N*N方格上找吃的,每一个点(x,y)有一些吃的,FatMouse从(0,0)的出发去找吃的。每次最多走k步,他走过的位置能够吃掉吃的。保证吃的数量在0-100。规定他仅仅能水平或者垂直走,每走一步。下一步吃的数量须要大于此刻所在位置,问FatMouse最多能够吃多少东西。
全栈程序员站长
2022/07/10
2170
Leetcode | 第8节:记忆化搜索,树(上)
今天我们来讲一讲记忆化搜索和树这个数据结构。记忆化搜索是对搜索算法的一个优化,涉及到记忆化搜索的题目都或多或少有一点技巧。至于树,它的定义非常简单,也有非常多的应用。同时它自己也在查找和排序中有自己的用武之地(例如二叉搜索树)。因此树的内容比较多也比较杂,我们可能没有办法一节给它说明白,也希望大家具备一些耐心~
学弱猹
2021/08/10
4020
Leetcode | 第8节:记忆化搜索,树(上)
HDU 4628 Pieces(状态压缩+记忆化搜索)
http://acm.hdu.edu.cn/showproblem.php?pid=4628 题意:给个字符窜,每步都可以删除一个字符窜,问最少用多少步可以删除一个字符窜 分析:状态压缩+记忆化搜索
用户1624346
2018/04/17
6990
【HDU 6171】Admiral(搜索+剪枝)
目标状态是第i行有i+1个i数字(i=0~5)共6行。给你初始状态,数字0可以交换上一行最近的两个和下一行最近的两个。求20步以内到目标状态的最少步数是多少。
饶文津
2020/06/02
3420
DFS+记忆化搜索 -- 简单练习
题意:你要去滑雪,你想在整个场地上找到一条最长的路好让你能够滑的尽兴!那么你要找出这条路
杨鹏伟
2020/09/11
4070
记忆化搜索简介「建议收藏」
记忆化搜索:算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存。
全栈程序员站长
2022/09/17
2170
相关推荐
记忆化搜索专题
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档