3235. Maximal-sum Subsequence

单点时限: 4.0 sec

内存限制: 256 MB

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

对于 的矩阵,如下序列都是合法的:

  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .

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

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

输入格式

第一行一个数 ,表示数据组数。

每一组数据第一行为一个正整数

接下来 行每行 个数表示这个矩阵。(每个元素大小在 之间)

输出格式

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

样例

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

提示

样例解释:选取序列

41 人解决,63 人已尝试。

49 份提交通过,共有 252 份提交。

4.9 EMB 奖励。

创建: 2 年,8 月前.

修改: 2 年,5 月前.

最后提交: 5 月,2 周前.

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

题目标签