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)


相关推荐

  • 点云显示工具(超详细教程)

    点云显示工具(超详细教程)

  • 集锦——浏览器每次访问自动更新网页,不用手工设置,附Google/firefox/Ie

    在做开发web开发的时候,经常要使用到浏览器来着进行调试,那么有时候自己修改了内容,可是在浏览器上还是没有显示出来,费了好久才发现是浏览器缓存的问题。还要强制刷新缓存 就是 Ctrl + F5。所以在开发时候,最好将自己的调试浏览器设置为访问自动刷新网页,不要使用页面的缓存。下面就是常用开发浏览器的设置:1. Chrome 浏览器打开到开发者模式:将Disable cache

  • 美化包软件_手机音量进度条插件下载

    美化包软件_手机音量进度条插件下载前言在我们进行自动化测试的时候,用例往往是成百上千,执行的时间是几十分钟或者是小时级别。有时,我们在调试那么多用例的时候,不知道执行到什么程度了,而pytest-sugar插件能很好解决我们的痛点。

  • 教你win10系统显卡驱动安装失败的解决方法

    教你win10系统显卡驱动安装失败的解决方法我们日常在对电脑的使用过程中,经常都会遇到这样或那样的问题。比如说win10系统显卡驱动安装失败该怎么办呢?别着急,还有小编在呢?接下来小编就来告诉大家win10电脑系统显卡驱动安装失败怎么解决。详细教你win10系统显卡驱动安装失败怎么办:方法一,删除之前的显卡驱动文件重新安装1,首先,右键点击“此电脑”,菜单栏选择“管理”。2,进入计算机管理界面后,点击“设备管理器”,然后在界面右侧展开“显示适配器”选项,并右键点击显卡驱动程序,菜单栏选择“属性”下一步。3,点击“卸载设备”。4,显卡

  • Lightroom人像磨皮滤镜插件portraiture Mac版

    Lightroom人像磨皮滤镜插件portraiture Mac版本次小编为您带来了Portraiture3forLightroomforMac,这是一款适用于Lightroom的lr人像磨皮滤镜插件。lr磨皮插件portraitureMac版功能非常强大,能够快速对图像中的皮肤,眉毛,头发,眼睛瞪部位进行磨皮修饰,去除瑕疵,同时为您保持皮肤的色泽!链接:https://pan.baidu.com/s/1U0QVMQ6Qa8F5NITbBVr3…

  • AsyncHandler

    AsyncHandler

发表回复

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

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