3630: 牛牛的 RPG 游戏(第一轮04)
题目描述
牛牛最近在玩一款叫做“地牢迷宫”的游戏，该游戏中的每一层都可以看成是一个 n*m 的二维棋盘，牛牛从左上角起始的(1,1)点移动到右下角的(n,m)点。
游戏中的每一个格子都会触发一些事件，这些事件将会影响玩家的得分。
具体来说，每到一个格子玩家触发事件时，首先会立即获得一个收益得分 val(i,j)。 注意这个得分不一定是正的，当它的值为负时将会扣除玩家一定的分数。
同时这个事件还会对玩家造成持续的影响，直到玩家下一次触发其他事件为止， 每走一步，玩家都会获得上一个事件触发点 buff(i,j)的得分。
在游戏开始时牛牛身上还没有任何的 buff，所以在牛牛还未触发任何事件之前每 走一步都不会产生任何影响。
牛牛使用“潜行者”这个职业，所以他路过地牢中的格子时， 可以选择不去触发这 些事件。
同时牛牛是一个速通玩家，想要快速的到达终点，所以他每次只会选择往右走或 者往下走。
牛牛想要知道，他玩游戏可以获得的最大得分是多少，你能告诉他么。
输入
第一行输入两个正整数 n,m
接下来输入 n 行，每行输入 m 个整数buff(i,j)表示该事件出发点被触发后，直 到下一次触发事件，每移动一步改变的得分。
接下来输入 n 行，每行输入 m 个整数val(i, j)表示该事件出发点被触发后，分数 的该变量。
输入保证，对于起点和终点,val(1, 1) = val(n, m) = buff(1, 1) = buff(n, m) = 0。
输出
输出仅一行一个非负整数，表示牛牛从左上角走到右下角的最多得分。
样例输入 复制
3 3
0 1 -80
1 -1000 0
-100 0 0
0 -5 100
2 100 0
100 -1 0样例输出 复制
20提示
【样例 1 说明】
一开始在(1,1)点，得分 0，身上没有事件影响buff 。
接下来移动到(1,2)点，不触发事件，得分 0，身上没有事件影响buff 。
接下来移动到(1,3)点，触发事件，得分 100，身上有buff影响，每走一步减少 80 点得分。
接下来移动到(2,3)点，移动时扣除 80 得分，身上还有20 点得分，然后触发事件，
得分+0，同时 buff 被替换为每走一步+0。
接下来移动到(3,3)点，结束游戏，总得分 20。
【数据范围】
对于前10%的测试数据，保证1 ≤ n, m ≤ 5 对于前20%的测试数据，保证1 ≤ n, m ≤ 30 对于另20%的测试数据，保证min(n, m) = 1 对于另20%的测试数据，保证min(n, m) = 2
对于另10%的测试数据，保证输入的buff(i,j) = 0
对于100%的测试数据，保证n × m ≤ 105, |val(i,j)| ≤ 104 ,
对于起点和终点, val(1, 1) = val(n, m) = buff(1, 1) = buff(n, m) = 0