首页 > 【洛谷P1508】吃吃吃

【洛谷P1508】吃吃吃

题目背景

问世间,青春期为何物?

答曰:“甲亢,甲亢,再甲亢;挨饿,挨饿,再挨饿!”

题目描述

正处在某一特定时期之中的李大水牛由于消化系统比较发达,最近一直处在饥饿的状态中。某日上课,正当他饿得头昏眼花之时,眼前突然闪现出了一个nm(n and m<=200)的矩型的巨型大餐桌,而自己正处在这个大餐桌的一侧的中点下边。餐桌被划分为了nm个小方格,每一个方格中都有一个圆形的巨型大餐盘,上面盛满了令李大水牛朝思暮想的食物。李大水牛已将餐桌上所有的食物按其所能提供的能量打了分(有些是负的,因为吃了要拉肚子),他决定从自己所处的位置吃到餐桌的另一侧,但他吃东西有一个习惯——只吃自己前方或左前方或右前方的盘中的食物。

由于李大水牛已饿得不想动脑了,而他又想获得最大的能量,因此,他将这个问题交给了你。

每组数据的出发点都是最后一行的中间位置的下方!

输入输出格式

输入格式:

[输入数据:]

第一行为m n.(n为奇数),李大水牛一开始在最后一行的中间的下方

接下来为m*n的数字距阵.

共有m行,每行n个数字.数字间用空格隔开.代表该格子上的盘中的食物所能提供的能量.

数字全是整数.

输出格式:

[输出数据:]

一个数,为你所找出的最大能量值.

--------------------------------------------------------------------------------------------------分割线------------------------------------------------------------------------------------------------------------------

打倒DP暴政,世界属于记搜!

虽然我不知道怎么回事这道题用记搜比DP慢就是了

这道题有个小坑点:有负数点(而且必须吃),所以如果一开始把记忆数组f赋值成-1就会挂。如果是DP就会WA,鬼知道为什么用记搜就会RE。

代码:

#include
using namespace std;
int a[202][202];
int f[202][202];
bool vis[202][202];//存放这个点有没有访问过
int n,m;
int my_max(int x,int y,int z)//三个数比较大小
{int ans=x;if (ans0)&&(y+i<=n)&&(x-1>0))f[x][y]=max(f[x][y],dfs(x-1,y+i)+a[x][y]);//记忆化}vis[x][y]=true;return f[x][y];
}
int main()
{cin>>n>>m;memset(a,-9999,sizeof(a));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}memset(f,-0x3f,sizeof(f));//初始化memset(vis,false,sizeof(vis));for(int i=1;i<=m;i++) f[1][i]=a[1][i],vis[1][i]=true;//第一排都无法再向下搜索了dfs(n+1,m/2+1);cout<

转载于:https://www.cnblogs.com/mengmengdezhongyezijiang/p/8263492.html

更多相关:

  •         Apache POI是一个开源的利用Java读写Excel,WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码:package com.xing.studyTest.poi;import java.io.FileInputSt...

  • 要取得[a,b)的随机整数,使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。 要取得a到b之间的...

  • 利用本征图像分解(Intrinsic Image Decomposition)算法,将图像分解为shading(illumination) image 和 reflectance(albedo) image,计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 题目:面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制: 1 <= 数组长度 <= 50000 解题: cl...

  • 题目:二叉搜索树的后序遍历序列 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:      5     /    2   6   /  1   3示例 1: 输入: [1,6,3,2,5] 输出...

  • 把字符串看作是26进制的数,从后往前翻译,那么就可以把两个串变成对应的26进制的数字,那么只要把两个数加起来除以二就得到中间的串对应的数了,同理再转化回来就行了。但是这样会有一个问题就是串的长度有2e5,26的2e5次方显然不可求,所以需要对每一位进行手动的加和运算。对于两个串,我们假设a串从后往前的每一位对应的数值为a0, a1,...

  • 中国剩余定理说白了就是小学时候的韩信点兵的完全版。给定一系列数,给定条件是一个数MOD这一些列数的结果,问你最后这个数最少为多少。 抽象出来就是N个同余方程,利用扩展GCD就可以求得这一结果,本题给定的数都是互质的,因此处理起来就简单了。 代码如下: #include #include #inc...