hdu1078(记忆化搜索)

摘要:
含义:给定n*n网格,每个网格中都有一些食物。值得记住的是,当老鼠每次走k步时,它可以吃最多的食物。它已经被重写了n次。在之前的搜索中没有注意到的一个小地方导致了重复的ac代码:#include#incluse #include<string h>使用namespacestd;intdp[110][110],s[110][110];整数n,k,t[4][2]={1,0,-1,0,0,1,0,-1};Intdfs{intmaxx=0,xx,yy,ans;if(!Dp[x][y]){for{for{xx=x+t[j][0]*i;yy=y+t[j][1]*i;if//这是错误的。您不能首先判断s[xx][yy],否则re{ans=dfs;ifmaxx=ans;}}将出现Dp[x][y]=maxx+s[y];}返回dp[x][y];}intmain(){当{ifbreak;forforscanf;memset;intsum=dfs(0,0);printf;}返回0;}

题意:给出n*n的格子,每个各自里面有些食物,问一只老鼠每次走最多k步所能吃到的最多的食物

这道题目,值得我记住它,re了n次,以前写搜索没有注意的一个小地方,导致re这么多次的

ac代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[110][110],s[110][110];
int n,k,t[4][2]={1,0,-1,0,0,1,0,-1};
int dfs(int x,int y)
{
    int maxx=0,xx,yy,ans;
    if(!dp[x][y])
    {
        for(int i=1;i<=k;i++)
        {
            for(int j=0;j<4;j++)
            {
                 xx=x+t[j][0]*i;
                 yy=y+t[j][1]*i;
                if(xx>=0&&xx<n&&yy>=0&&yy<n&&s[xx][yy]>s[x][y])
                {
                     ans=dfs(xx,yy);
                    if(ans>maxx)
                    maxx=ans;
                }
            }
        }
        dp[x][y]=maxx+s[x][y];
    }
    return dp[x][y];
}
int main()
{
    while(scanf("%d%d",&n,&k)>0)
    {
        if(n==-1&&k==-1)
        break;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        scanf("%d",&s[i][j]);
        memset(dp,0,sizeof(dp));
        int sum=dfs(0,0);
        printf("%d
",sum);
    }
    return 0;
} 

re代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[110][110],s[110][110];
int n,k,t[4][2]={1,0,-1,0,0,1,0,-1};
int dfs(int x,int y)
{
    int maxx=0,xx,yy,ans;
    if(!dp[x][y])
    {
        for(int i=1;i<=k;i++)
        {
            for(int j=0;j<4;j++)
            {
                 xx=x+t[j][0]*i;
                 yy=y+t[j][1]*i;
                if(s[xx][yy]>s[x][y]&&xx>=0&&xx<n&&yy>=0&&yy<n)   //这里错了,不能将s[xx][yy]先判断,否则出现re 
                {
                     ans=dfs(xx,yy);
                    if(ans>maxx)
                    maxx=ans;
                }
            }
        }
        dp[x][y]=maxx+s[x][y];
    }
    return dp[x][y];
}
int main()
{
    while(scanf("%d%d",&n,&k)>0)
    {
        if(n==-1&&k==-1)
        break;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        scanf("%d",&s[i][j]);
        memset(dp,0,sizeof(dp));
        int sum=dfs(0,0);
        printf("%d
",sum);
    }
    return 0;
} 

免责声明:文章转载自《hdu1078(记忆化搜索)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Linux 安装oracle10g 配置dataguard 介绍和步骤ubuntu 环境下pycharm的 安装与激活教程 以及错误解决方法下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

Linux snmp导入MIB库

Linux中使用的net-snmp带有一些标准MIB,但世界上有无数种支持snmp的设备,每个制造商都有自己的定义。这些定义不能包含在net-snmp附带的MIB中。因此,如果要正确轮询此类设备,必须加载制造商自己的MIB文件。...

fullcalendar日历控件知识点集合

除非对于极少的特殊需求,fullcalendar向我们提供的接口不足以满足,才会去改动fullcalendar本身的js文件。这些会议安排一般是保存在server的,在每次页面载入时,fullcalendar得到会议安排的集合,然后依照当中的日期去把事件描绘到日历相应的地方。...

MyBatisPlus使用

简介MyBatis Plus是MyBatis的增强工具。基于MyBatis,只进行了增强而不进行更改。它旨在简化开发并提高效率。...

mini.DataGrid使用说明

√√√ ajaxOptionsObjectajax配置对象。√√√ idFieldString是行数据的唯一字段。设置为“client”之后,客户端将排序√√√√ totalCountNumber记录总数√√√ defaultColumnWidthNumber默认列宽100√√√√ showColumnsBoolean显示标头true√√√√ showPag...

beego

Charset=utf8“)56//参数4(可选)设置最大空闲连接7//参数5modelorm.RegisterModelRegisterModelWithPrefix。使用表名前缀orm.RegisterModelWithPrefixbeego自动创建表。1//参数1使用默认数据库ORM接口使用1//查询操作2funread(){3o:=ORM.NewOr...

差分方程的零输入响应与零状态响应

差分方程的迭代分析方法有以下缺点:没有闭合解,不利于数学分析。某个时间的输出只能从头开始计算。本文介绍了差分方程的零输入响应和零状态响应分析方法。对于系统,这种分析方法可以很好地表达系统响应的物理意义=Y[-1]=0$Input Y[n]。回顾零输入响应和零状态响应的迭代计算,我们发现以下规则:$egin{align*}y[0]&=-&qqu...