QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[0]

# 4109. 探险路线

Statistics

你所面对的丛林,可以被刻画为 nm 列的格点图,其中第 i 行第 j 列的格子代表了一块区域,每个格子有整数权值 v(i,j)(可能为负),表明了访问这一块区域的收益或代价。每一个格子最多只能被访问一次,且不可走出地图的边界,你被要求从第一行第一列出发,到第 n 行第 m 列结束,你的目标是最大化途经的所有格子的权值和。

因为一些缘故,你的探险路线受到了一些限制。起初你在起点,之后每一天的行动中,首先你需要选择上下左右中的某一个方向,沿着这个方向走 0 步(也就是不走)或任意步;之后重新选择一个方向(可以与原来方向相同,也可以是不同的方向),沿着这个方向一直走下去,走到地图的某个边界位置结束这一天的探险。探险可以有任意多天,每一天探险结束的边界位置就是第二天的起点位置,除非这一天就是探险的结束。注意,因为每一块格子只能被访问一次,且你最终的结束点必须是第 n 行第 m 列的位置,所以你需要谨慎计划每一天的路线。你希望知道最优方案下,整个探险之旅的收益有多大,即你可以获得的权值和最大是多少。

输入格式

第一行输入两个整数,分别表示总行数 n 与总列数 m

之后 n 行,每行有 m 个整数。其中第 i 行第 j 列的整数对应了访问第 i 行第 j 列区域的收益或代价。

输出格式

输出一个整数,表示最优探险路线中所有被访问格子的权值和。

样例数据

样例输入

10 10
+1 +1 +1 +1 +1 -1 -1 -1 -1 -1
-1 -1 +1 +1 +1 -1 -1 -1 -1 -1
-1 -1 +1 +1 +1 +1 +1 +1 +1 +1
+1 +1 +1 +1 -1 -1 -1 -1 -1 +1
+1 -1 -1 +1 -1 -1 -1 -1 -1 +1
+1 +1 +1 +1 -1 -1 -1 -1 -1 +1
+1 +1 +1 +1 +1 +1 +1 +1 +1 +1
+1 -1 -1 -1 -1 -1 -1 -1 -1 -1
+1 +1 +1 +1 -1 +1 +1 +1 +1 +1
-1 -1 -1 +1 +1 +1 -1 -1 -1 +1

样例输出

53

子任务

对于 10% 的数据,n,m5

对于 40% 的数据,n,m40

对于 70% 的数据,n,m100

对于所有数据,5n,m800,区域收益或代价的绝对值在 100000 以内。