矩阵取数(Hard Version)
测试数据来自 nnu_contest/1265
矩阵取数(Hard Version)
时间限制:3s
空间限制:64MB
题目描述
给定正整数\(n,m\),在\(n*m\)的矩阵中取若干个数字,但任意两个取出的数字在矩阵中的位置不能相邻。
(若A位置与B位置在矩阵的同一行,但列号相差1,或它们在同一列,但行号相差1,则称它们相邻。
注意:左上方、左下方、右上方、右下方不算相邻。)
问:取出数字的最大和是多少?
输入格式
第一行两个整数\(n,m\),表示矩阵大小。
接下来\(n\)行每行\(m\)个整数,表示这个矩阵
输出格式
一个整数,表示答案。
样例输入1
5 4
9 41 33 8
50 12 33 49
28 26 44 42
29 41 40 11
16 1 46 20
样例输出1
298
样例输入2
9 9
30 13 12 50 9 23 29 11 31
2 36 4 40 14 15 46 50 1
12 18 13 45 41 37 33 47 43
29 21 28 50 15 3 38 45 49
5 46 10 22 4 49 28 26 33
1 2 28 22 50 17 15 7 1
8 30 46 2 48 34 44 31 34
24 15 48 16 4 21 12 1 22
49 2 37 10 21 50 10 32 8
样例输出2
1080
数据范围及限制
\(1\le n,m \le 15\)
\(0<a_{ij}<10^4\)
信息
- ID
- 1067
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者