P1508 Likecloud-吃、吃、吃【洛谷算法习题】-北京尧图网络

P1508 Likecloud-吃、吃、吃网页链接P1508 Likecloud-吃、吃、吃题目背景问世间青春期为何物答曰“甲亢甲亢再甲亢挨饿挨饿再挨饿”题目描述正处在某一特定时期之中的李大水牛由于消化系统比较发达最近一直处在饥饿的状态中。某日上课正当他饿得头昏眼花之时眼前突然闪现出了一个n × m ( n , m ≤ 200 ) n \times m(n,m \le 200)n×m(n,m≤200)的矩型的巨型大餐桌而自己正处在这个大餐桌的一侧的中点下边。餐桌被划分为了n × m n \times mn×m个小方格每一个方格中都有一个圆形的巨型大餐盘上面盛满了令李大水牛朝思暮想的食物。李大水牛已将餐桌上所有的食物按其所能提供的能量打了分有些是负的因为吃了要拉肚子他决定从自己所处的位置吃到餐桌的另一侧途径的所有食物都必须吃掉不能不吃。但他吃东西有一个习惯——只吃自己前方或左前方或右前方的盘中的食物。由于李大水牛已饿得不想动脑了而他又想获得最大的能量因此他将这个问题交给了你。每组数据的出发点都是最后一行的中间位置的下方输入格式第一行为m mm、n nnn nn为奇数李大水牛一开始在最后一行的中间的下方。接下来为m × n m \times nm×n的数字矩阵。矩阵共有m mm行每行n nn个数字数字间用空格隔开代表该格子上的盘中的食物所能提供的能量。数字全是整数且绝对值不超过10 5 10^5105。输出格式一个数为你所找出的最大能量值。输入输出样例 #1输入 #16 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输出 #141说明/提示快吃快吃快吃解题思路本题是动态规划矩阵路径最大和的经典题型属于数字三角形的扩展版利用路径可逆性将自底向上的问题转化为自顶向下递推高效求解最大能量路径。1. 问题转化人站在最后一行下方每次可向正前、左前、右前移动最终到达第一行任意位置求路径最大能量和。由于路径的能量和具有可逆性该问题等价于从第一行任意位置出发每次向正下、左下、右下移动最终到达最后一行的中间三列求路径最大能量和。转化后可按行从上到下顺序递推实现更直观。2. 动态规划设计状态定义dp[i][j]表示到达第i行第j列时能获得的最大能量总和。初始状态第一行的每个格子初始值为自身能量值对应起点可在第一行任意位置。状态转移第i行第j列的位置可由上一行的三个位置转移而来左上i-1,j-1、正上i-1,j、右上i-1,j1。取三者中的最大值加上当前格子的能量值即为当前位置的最大能量d p [ i ] [ j ] max ⁡ ( d p [ i − 1 ] [ j − 1 ] , d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j 1 ] ) v a l [ i ] [ j ] dp[i][j] \max(dp[i-1][j-1],\ dp[i-1][j],\ dp[i-1][j1]) val[i][j]dp[i][j]max(dp[i−1][j−1],dp[i−1][j],dp[i−1][j1])val[i][j]最终结果原问题起点在最后一行中点下方第一步可到达最后一行的中间三列左、中、右因此最终答案为最后一行中间三个位置的dp值的最大值。3. 复杂度分析时间复杂度O ( m × n ) O(m \times n)O(m×n)m行n列每个格子仅需一次转移计算200×200规模下运算量极小。空间复杂度O ( m × n ) O(m \times n)O(m×n)使用二维数组存储dp状态本题数据规模无需额外空间优化。总结核心逻辑将自底向上的路径问题转化为自顶向下的动态规划递推通过三方向取最大值完成状态转移最终取终点范围内的最大值作为结果。关键操作路径可逆性等价转化、三方向状态取最大转移、终点三列取最大值。效率保障线性遍历矩阵单步转移计算运行速度极快。代码简要说明变量定义n、m分别为矩阵的行数和列数与题目输入的m行n列对应顺序做了调换二维数组dp存储动态规划状态初始全为0。数据读入直接将矩阵能量值读入dp数组第一行天然作为动态规划的初始状态。DP递推从第二行开始逐行遍历每个位置从上一行的左、中、右三个位置取最大值加上当前格子能量更新dp值。结果计算取最后一行中间三列m/2、m/21、m/22的dp最大值输出对应原问题第一步可到达的三个起点位置。边界说明代码采用0值初始化数组矩阵左右边界会引用到矩阵外的0值。当合法前驱均为负数时可能出现偏差更严谨的写法是将数组初始化为负无穷仅对合法位置赋值。输入优化关闭流同步并解绑tie提升数据读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,m,dp[255][255];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(dp,0,sizeof(dp));cinnm;for(ll i1;in;i)for(ll j1;jm;j)cindp[i][j];for(ll i2;in;i)for(ll j1;jm;j)dp[i][j]max(max(dp[i-1][j],dp[i-1][j1]),dp[i-1][j-1])dp[i][j];coutmax(dp[n][m/21],max(dp[n][m/2],dp[n][m/22]));return0;}

P1508 Likecloud-吃、吃、吃【洛谷算法习题】

相关推荐

小红的数字拆解【牛客tracker 每日一题】

零基础单片机开发入门系列：8天从裸机开发到打通RTOS

MLX框架入门：为什么Inkling-mlx-2bit是Apple Silicon的最佳选择

更多资讯

STM32H743双核实战指南：480MHz性能落地的关键陷阱与决策逻辑

离线可用的软考机考模拟系统：技术选型与提分实践

ruflo：规则驱动的流程引擎如何实现动态路由与规则集解耦

直流减速电机PI闭环控制实战：从原理到参数整定

棒板电极空气电晕放电仿真：从电场建模到击穿电压预测

ITIL 4迁移的五大隐形陷阱：从价值流到数据治理的落地指南

今日更新

在S3C2410上移植Nucleus RTOS：启动、驱动与实时性调优实战

2026年Turnitin降重降AI二合一红黑榜：能过和别碰

2026期刊投稿AI写作工具实测：6款打分谁更值得用

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？