会员专享
请先
登录 ，登录后可使用今日免费解锁；
开通会员 后可解锁完整内容。
解题思路
两个机器人的合法路径长度都是 h + w − 2 h+w-2 h + w − 2
走了 t t t A A A ( t − c 1 , c 1 ) (t-c_1,c_1) ( t − c 1 , c 1 ) B B B ( t − ( w − 1 − c 2 ) , c 2 ) (t-(w-1-c_2),c_2) ( t − ( w − 1 − c 2 ) , c 2 )
用 d p [ c 1 ] [ c 2 ] dp[c_1][c_2] d p [ c 1 ] [ c 2 ] A A A c 1 c_1 c 1 B B B c 2 c_2 c 2
A A A B B B 如果这一步两人落到同一格，该转移非法。不同时刻经过同一格是允许的，价值会加两次。
起点先把 v 0 , 0 + v 0 , w − 1 v_{0,0}+v_{0,w-1} v 0 , 0 + v 0 , w − 1 h + w − 2 h+w-2 h + w − 2 A A A w − 1 w-1 w − 1 B B B 0 0 0
题目内容
在智能物流中心里，货架排列成一个 h h h w w w ( i , j ) (i,j) ( i , j ) v i , j v_{i,j} v i , j A A A ( 0 , 0 ) (0,0) ( 0 , 0 ) ( h − 1 , w − 1 ) (h-1,w-1) ( h − 1 , w − 1 ) B B B ( 0 , w − 1 ) (0,w-1) ( 0 , w − 1 ) ( h − 1 , 0 ) (h-1,0) ( h − 1 , 0 )
两台机器人同时出发，并且每一步都必须走一格，因此它们的步数始终保持相同。每当机器人到达一个货架，就会把该货架的货物价值累加到自己的盘点结果中。货架之间的通道非常狭窄，任意时刻两台机器人不能站在同一个货架上；但同一个货架可以在不同时刻被两台机器人分别经过。
管理员需要为两台机器人规划满足上述限制的路线，使得它们累加的货物价值总和尽可能大。请计算这个最大总和。
约束条件
行数 h h h w w w 3 ≤ h , w ≤ \le h,w \le ≤ h , w ≤ 100。
每个货架价值 v i , j v_{i,j} v i , j 0 ≤ v i , j ≤ \le v_{i,j} \le ≤ v i , j ≤ 100000。
输入描述
第一行包含两个整数 h h h w w w
接下来 h h h w w w v i , j v_{i,j} v i , j
输出描述
输出一个整数，表示两台机器人能够取得的货物价值总和的最大值。
样例1
输入
3 3
1 2 3
4 5 6
7 8 9
输出
58
说明
矩阵大小为 3 × 3 3\times 3 3 × 3 ( 0 , 0 ) → ( 1 , 0 ) → ( 1 , 1 ) → ( 1 , 2 ) → ( 2 , 2 ) (0,0)\to(1,0)\to(1,1)\to(1,2)\to(2,2) ( 0 , 0 ) → ( 1 , 0 ) → ( 1 , 1 ) → ( 1 , 2 ) → ( 2 , 2 ) 1+4+5+6+9=25。机器人 B 选择 ( 0 , 2 ) → ( 1 , 2 ) → ( 2 , 2 ) → ( 2 , 1 ) → ( 2 , 0 ) (0,2)\to(1,2)\to(2,2)\to(2,1)\to(2,0) ( 0 , 2 ) → ( 1 , 2 ) → ( 2 , 2 ) → ( 2 , 1 ) → ( 2 , 0 ) 3+6+9+8+7=33。
两条路线在对应时刻的位置分别为 ( 0 , 0 ) , ( 1 , 0 ) , ( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 2 ) (0,0),(1,0),(1,1),(1,2),(2,2) ( 0 , 0 ) , ( 1 , 0 ) , ( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 2 ) ( 0 , 2 ) , ( 1 , 2 ) , ( 2 , 2 ) , ( 2 , 1 ) , ( 2 , 0 ) (0,2),(1,2),(2,2),(2,1),(2,0) ( 0 , 2 ) , ( 1 , 2 ) , ( 2 , 2 ) , ( 2 , 1 ) , ( 2 , 0 ) 25+33=58，这也是可行路线中的最大值。
样例2
输入
3 3
0 0 0
0 5 0
0 0 0
输出
5
说明
在给定矩阵中，只有 ( 1 , 1 ) (1,1) ( 1 , 1 ) 5，其余均为 0。从两个起点到达 ( 1 , 1 ) (1,1) ( 1 , 1 ) 2 步移动；如果两台机器人都经过该格，它们会在出发后经过 2 步移动时同时到达，从而发生碰撞。因此最多只有一台机器人能取得该价值 5。
例如机器人 A 走 ( 0 , 0 ) → ( 1 , 0 ) → ( 1 , 1 ) → ( 1 , 2 ) → ( 2 , 2 ) (0,0)\to(1,0)\to(1,1)\to(1,2)\to(2,2) ( 0 , 0 ) → ( 1 , 0 ) → ( 1 , 1 ) → ( 1 , 2 ) → ( 2 , 2 ) ( 0 , 2 ) → ( 1 , 2 ) → ( 2 , 2 ) → ( 2 , 1 ) → ( 2 , 0 ) (0,2)\to(1,2)\to(2,2)\to(2,1)\to(2,0) ( 0 , 2 ) → ( 1 , 2 ) → ( 2 , 2 ) → ( 2 , 1 ) → ( 2 , 0 ) 5+0=5。
样例3
输入
3 4
0 0 0 0
0 0 0 0
0 0 0 0
输出
0
说明
矩阵大小为 3 × 4 3\times 4 3 × 4 0。无论两台机器人选择哪条满足移动限制且不发生碰撞的路线，途经货架的价值总和始终为 0，因此最大总和为 0。
