[Sdoi2016]探险路线

内存限制：512 MiB 时间限制：10 Sec

提交提交记录讨论

你所面对的丛林，可以被刻画为n行m列的格点图，其中第i行第j列的格子代表了一块区域，每个格子有整数权值v(

i,j)（可能为负），表明了访问这一块区域的收益或代价。每一个格子最多只能被访问一次，且不可走出地图的边

界，你被要求从第一行第一列出发，到第n行第m列结束，你的目标是最大化途经的所有格子的权值和。因为一些缘

故，你的探险路线受到了一些限制。起初你在起点，之后每一天的行动中，首先你需要选择上下左右中的某一个方

向，沿着这个方向走0步（也就是不走）或任意步；之后重新选择一个方向（可以与原来方向相同，也可以是不同

的方向），沿着这个方向一直走下去，走到地图的某个边界位置结束这一天的探险。探险可以有任意多天，每一天

探险结束的边界位置就是第二天的起点位置，除非这一天就是探险的结束。注意，因为每一块格子只能被访问一次

，且你最终的结束点必须是第n行第m列的位置，所以你需要谨慎计划每一天的路线。你希望知道最优方案下，整个

探险之旅的收益有多大，即你可以获得的权值和最大是多少。

第一行输入两个整数，分别表示总行数n与总列数m。之后n行，每行有m个整数，保证绝对值在100000以内。其中第

i行第j列的整数对应了访问第i行第j列区域的收益或代价。3<=n<=800且3<=m<=800

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

样例输入


			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

#4601. [Sdoi2016]探险路线

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示