3235. Maximal-sum Subsequence

单点时限: 4.0 sec

内存限制: 256 MB

给一个 $N \times N$ 的矩阵 $M$,可以取连续的一段数(必须是横着或者竖着或者斜着,这个矩阵是循环的,具体如下)。要求找到一个子序列,使得这个序列的和最大。

对于 $N=8$ 的矩阵,如下序列都是合法的:

  • $M_{2,1}, M_{2,2}, M_{2,3}, M_{2,4}, M_{2,5}, M_{2,6}, M_{2,7}, M_{2,8}$.
  • $M_{2,2}, M_{2,3}, M_{2,4}$.
  • $M_{2,6}, M_{2,7}, M_{2,8}, M_{2,1}, M_{2,2}$.
  • $M_{4,3}, M_{5,3}, M_{6,3}, M_{7,3}$.
  • $M_{1,2}, M_{2,3}, M_{3,4}, M_{4,5}$.
  • $M_{2,4}, M_{3,3}, M_{4,2}, M_{5,1}$.
  • $M_{3,3}, M_{4,2}, M_{5,1}, M_{1,5}$.
  • $M_{5,6}$.

一个元素不可取多次,取的必须是连续的一段。

可以什么都不取(即答案为 $0$)。

输入格式

第一行一个数 $T$ $(T \leq 30)$,表示数据组数。

每一组数据第一行为一个正整数 $N$ $(1 \leq N \leq 1000)$。

接下来 $N$ 行每行 $N$ 个数表示这个矩阵。(每个元素大小在 $-32768$ 到 $32767$ 之间)

输出格式

每组数据一行表示最大的序列和。

样例

Input
1
4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2
Output
24

提示

样例解释:选取序列 $M_{3,4}, M_{4,3}, M_{1,2}$。

45 人解决,68 人已尝试。

54 份提交通过,共有 267 份提交。

4.8 EMB 奖励。

创建: 5 年,4 月前.

修改: 5 年,1 月前.

最后提交: 3 月前.

来源: 2017 华东理工上海高校邀请赛

题目标签