洛谷——1508 Likecloud-吃、吃、吃
2024-08-30 01:01:51
题目背景
问世间,青春期为何物?
答曰:“甲亢,甲亢,再甲亢;挨饿,挨饿,再挨饿!”
题目描述
正处在某一特定时期之中的李大水牛由于消化系统比较发达,最近一直处在饥饿的状态中。某日上课,正当他饿得头昏眼花之时,眼前突然闪现出了一个n*m(n and m<=200)的矩型的巨型大餐桌,而自己正处在这个大餐桌的一侧的中点下边。餐桌被划分为了n*m个小方格,每一个方格中都有一个圆形的巨型大餐盘,上面盛满了令李大水牛朝思暮想的食物。李大水牛已将餐桌上所有的食物按其所能提供的能量打了分(有些是负的,因为吃了要拉肚子),他决定从自己所处的位置吃到餐桌的另一侧,但他吃东西有一个习惯——只吃自己前方或左前方或右前方的盘中的食物。
由于李大水牛已饿得不想动脑了,而他又想获得最大的能量,因此,他将这个问题交给了你。
每组数据的出发点都是最后一行的中间位置的下方!
输入输出格式
输入格式:
[输入数据:]
第一行为m n.(n为奇数),李大水牛一开始在最后一行的中间的下方
接下来为m*n的数字距阵.
共有m行,每行n个数字.数字间用空格隔开.代表该格子上的盘中的食物所能提供的能量.
数字全是整数.
输出格式:
[输出数据:]
一个数,为你所找出的最大能量值.
输入输出样例
输入样例#1:
6 7 16 4 3 12 6 0 3 4 -5 6 7 0 0 2 6 0 -1 -2 3 6 8 5 3 4 0 0 -2 7 -1 7 4 0 7 -5 6 0 -1 3 4 12 4 2
输出样例#1:
41
说明
快吃!快吃!快吃!
代码
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; ][],f[][]; int main() { scanf("%d%d",&n,&m); ;i<=n;i++) ;j<=m;j++) scanf("%d",&a[i][j]); ;i<=n+;i++) ;j<=m;j++) f[i][j]=a[i][j]+max(max(f[i-][j],f[i-][j+]),f[i-][j-]); printf(][m/+]); ; }
思路:
这是一个典型的棋盘DP!
只是需要把结束的点改为f[n+1][m/2+1]即为最后一行中间点的下方。
从头开始枚举每一条路径,最后找到达这一点的最大值
最新文章
- 部署 instance 到 VXLAN - 每天5分钟玩转 OpenStack(112)
- MVC中的默认Model绑定者DefaultModelBinder
- 如何提高redmine的访问速度
- 使用 Redis 实现排行榜功能 (转载 https://segmentfault.com/a/1190000002694239)
- ROS 使用自带和usb摄像头获取图像
- [转]Dll注入经典方法完整版
- Caused by: android.system.ErrnoException: open failed: EACCES (Permission denied)
- requirejs、backbone.js配置
- Nginx部署ThinkPHP项目的办法
- Android 动画特效
- rxjava各种使用场景
- Android UI-开源框架ImageLoader的完美例子
- [BZOJ 3626] [LNOI2014] LCA 【树链剖分 + 离线 + 差分询问】
- POJ 2774 最长公共子串
- CodeForces 446B DZY Loves Modification
- JavaScript(15)jQuery 选择器
- 简谈-Python一些常用的爬虫技巧
- 原生 JS 实现一个瀑布流插件
- php使用file_get_contents请求微信接口失败
- ReactNative Android之原生UI组件动态addView不显示问题解决
热门文章
- 【Todo】 cygwin下emacs中M-x shell 中出现乱码
- Spring.Net初认识——竹子整理
- 异步消息处理机制,UI更新
- Diycode开源项目 NodeListFragment分析
- 如何使用PowerShell管理Windows服务
- Intellij IDEA快捷键大全
- 【Combinations】cpp
- python-os模块及md5加密
- Spider_Man_6 の Scrapy(未完待续)
- 【LeetCode】Remove Duplicates from Sorted List(删除排序链表中的重复元素)