#P4601. [Sdoi2016]探险路线
[Sdoi2016]探险路线
[SDOI2016] 探险路线
题目描述
给定一个 行 列的地图,格子 的权值为 ,可能为负。你从 出发,最终到达 。每步在上下左右相邻格子间移动,不得走出地图,也不得再次经过任何已访问的格子。
探险以天为单位。每天先任选一个方向,沿该方向走若干步,也可走零步。然后再选一个方向,可以与第一次所选方向相同,沿该方向一直走到地图边界上的一个格子,当天结束。第一天从 开始,其余各天从前一天结束的位置继续。停在日与日的交界格子时只算访问一次。最后一天结束在 。天数不限。
求所有合法探险路线中,经过格子的权值和的最大值。起点和终点均计入权值和。
输入格式
第一行两个整数 。接下来 行,每行 个整数,第 行的第 个整数为 。
输出格式
输出一个整数,表示最大权值和。
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
数据范围
,。
| 数据比例 | 的上限 |
|---|---|
| 5 | |
| 40 | |
| 100 | |
| 800 |