#P4601. [Sdoi2016]探险路线

    ID: 1841 传统题 1000ms 512MiB 尝试: 41 已通过: 21 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS动态规划网格 DP线性 DP前后缀状态分解排序与序列处理一维前缀和滚动数组线性代数与代数矩阵转置CF2900

[Sdoi2016]探险路线

[SDOI2016] 探险路线

题目描述

给定一个 nn 行 mm 列的地图,格子 (i,j)(i,j) 的权值为 vi,jv_{i,j},可能为负。你从 (1,1)(1,1) 出发,最终到达 (n,m)(n,m)。每步在上下左右相邻格子间移动,不得走出地图,也不得再次经过任何已访问的格子。

探险以天为单位。每天先任选一个方向,沿该方向走若干步,也可走零步。然后再选一个方向,可以与第一次所选方向相同,沿该方向一直走到地图边界上的一个格子,当天结束。第一天从 (1,1)(1,1) 开始,其余各天从前一天结束的位置继续。停在日与日的交界格子时只算访问一次。最后一天结束在 (n,m)(n,m)。天数不限。

求所有合法探险路线中,经过格子的权值和的最大值。起点和终点均计入权值和。

输入格式

第一行两个整数 n,mn,m。接下来 nn 行,每行 mm 个整数,第 ii 行的第 jj 个整数为 vi,jv_{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

数据范围

3≤n,m≤8003\le n,m\le800,∣vi,j∣≤105|v_{i,j}|\le10^5。

数据比例 n,mn,m 的上限
10%10\% 5
40%40\% 40
70%70\% 100
100%100\% 800