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;}