HDOJ1078 记忆化搜索入门题 有详细的记忆化搜索模板程序

HDOJ1078 记忆化搜索入门题 有详细的记忆化搜索模板程序FatMouseandCheeseTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):10863    AcceptedSubmission(s):4625ProblemDescriptionFatMo

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

FatMouse and Cheese

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




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
  
  
  
37
 


Source
 


Recommend
We have carefully selected several similar problems for you:  
1080 
1074 
1081 
1025 
1158 


从(0,0)这个点出发,每次最多走K步,要求走到的格子数大于原来的,求问总那么多步后总和最大是多少。
记忆化搜索,很多路径有重复的,跟DP有些相似。
写了个DFS的记忆化搜索模板,作为参考。

记忆化搜索是自顶向下的,用递归实现,返回的最优解应该在出发点上

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cmath>
using namespace std;

const int  maxn =105;
int a[maxn][maxn],dp[maxn][maxn];
int n,k;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

int dfs(int x, int y){
    int tmp=0;
    for (int j=1;j<=k;j++){
      for (int i=0;i<4;i++){
        int xx=x+dx[i]*j; //k步是水平或竖直的
        int yy=y+dy[i]*j;
        if (xx<0 || yy<0 || xx>=n || yy>=n) continue;
        if (a[x][y]>=a[xx][yy]) continue;
        if (dp[xx][yy]) { //如果已经探索过了,就没必要继续深搜了
            tmp=max(tmp,dp[xx][yy]); //取最大值
            continue;
        }
        tmp=max(tmp,dfs(xx,yy)); //取所有方案中的最大值
      }
    }
    return dp[x][y]=a[x][y]+tmp;
}

int main(){
    std::ios::sync_with_stdio(false); //提高cin输入效率
    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));
        cout<<dfs(0,0)<<endl; //最优解在出发点上
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164447.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • msiexec用法详解

    msiexec用法详解在系统管理中,尤其是静默安装和卸载软件的时候,该命令就会经常用到,详细用户如下:(本文拷贝自微软网站)msiexec/Option<RequiredParameter>[OptionalParameter]安装选项 </package|/i><Product.msi> 安装或配置产品 /a<Product.msi&…

    2022年10月25日
  • 思科交换机AAA认证

    思科交换机AAA认证aaanew-modelusernameadminprivilege15passwordadminaaaauthenticationlogindefaultgrouptacacs+localaaaauthorizationexecdefaultgrouptacacs+localaaaaccountingexecdefaultstar…

  • 2022最新前端经典面试试题[通俗易懂]

    1,阐述清楚浮动的几种方式(常见问题)(1)父级div定义height原理:父级div手动定义height,就解决了父级div无法自动获取到高度的问题。优点:简单、代码少、容易掌握缺点:只适合高度固定的布局,要给出精确的高度,如果高度和父级div不一样时,会产生问题(2)父级div定义overflow:hidden原理:必须定义width或zoom:1,同时不能定义heigh…

  • 史上最全的Android基础教程+入门实战训练+处理技巧(建议收藏)|寻找C站宝藏

    史上最全的Android基础教程+入门实战训练+处理技巧(建议收藏)|寻找C站宝藏有个专栏包含了Android基础教程和入门实战训练的Android项目,还有各种Android处理技巧。没错,就是我从一年前开始做的Android王国专栏。为什么叫王国呢?因为我觉得接触任何领域的第一步都是先打好基础,然后再实战演练建筑高楼,最后学会各种技巧建筑围墙,这样你的知识王国就建好了,当然这座王国还在不断更新加固。赶紧收藏起来吧,在这里,0基础学会做app!

  • C# 通过 HtmlDocument 操作HTML节点

    C# 通过 HtmlDocument 操作HTML节点C#通过HtmlDocument操作HTML节点时,会发生不停地刷新的情况,在对html文档操作后加以判断即可解决这种问题。   PublicSubsetMainUlr(ByValWebBrowser1AsWebBrowser)           DimpElemAsHtmlElement=Nothing           即时信息页面          

  • 用Python进行web开发需要学习什么?「建议收藏」

    第一步:HTMLHTML是网页的核心,学好HTML是成为Web开发人员的基本条件。HTML很容易学习的,但也很容易误用,要学精还得费点功夫。  随着HTML5的发展和普及,了解HTML5也将成为Web开发人员的必修课。  涉及到网页外观时,就需要学习CSS了,它可以帮你把网页做得更美观。  利用HTML和CSS模拟一些你所见过的网站的排版和布局(色彩,图片,文字样式等等)。第二步:学习javascript,了解DOMJavaScript是一种能让你的网页更加生动活泼的程序语言。学习JavaScr

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号