logo AlgoBeat OnlineJudge
登录 注册

#101184. [BZOJ 1184] [HNOI2007]海盗分宝

内存限制:162 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

据说,加勒比海盗每次抢劫完,如果有金银珠宝等贵重物品,都会以特殊的仪式分宝。

他们首先将珠宝装在一个个边长为 的土陶立方体中,并在盖子上标记出珠宝的价值 。然后将这些盒子排列成一个长为 ,宽为 的矩形(如果珠宝不够,可能会用空的土陶盒占据空位,并在盖子上标记价值为 ),第 行第 列的土陶盒上标记的价值为 (其中 ,左下角的土陶盒所在位置为第一行第一列)。

海盗们按照功劳的大小,决定分宝的顺序,被轮到选取珠宝的海盗将被发给一个底面为 的矩形,高为 的木箱子,并要求用这个木箱子来装所选土陶盒,最后盖上木箱盖子。土陶盒的选取需要分批选取,要求每批土陶盒为一个等同于木箱底面的紧挨着的矩形区域,且木箱长为 的边必须与土陶盒摆成矩形时长为 的边平行。被选走的土陶盒所在位置在被选走后马上由空土陶盒填充。

海盗从土陶盒摆成的矩形底部正中出发,即从第一行的第 列的土陶盒的右下角出发,向上沿着据土陶盒摆成的矩形区域的最左边 的直线前进。如图中粗线箭头所示。

设第 批被选取的区域的左下角为第 行第 列的土陶盒, 必须满足 ,其中

且当 的时候, 必须满足 ,当 时, 必须满足 ,其中

pic1.png

输入格式

第一行包括 个正整数,这些正整数之间用一个空格隔开,这 个正整数依次为

从第二行到第 行,每行有 个整数,不妨将输入文件中第 行,第 列的整数记做 ),分别表示土陶盒上标记的珠宝价值,同一行的整数之间用一个空格隔开。

需注意的是:输入时 是从左上角的土陶盒开始,但在求解时左下角的那个土陶盒为第 行第 列的土陶盒。

输出格式

输出文件中的第一行为一个整数,是最多能得到的珠宝总价值

样例

样例输入 #1

10 12 3 2 3 5 2 3
0 0 0 1 0 1 1 1 9 1 1 1
1 1 2 1 1 1 0 0 8 2 1 8
1 0 1 0 1 6 1 1 0 0 1 1
1 1 2 1 2 1 1 1 3 1 1 1
0 1 0 1 1 1 2 1 6 0 2 1
1 1 0 1 0 1 1 2 1 1 1 0
1 0 1 1 1 0 1 0 1 1 0 1
1 1 0 1 1 1 9 0 0 1 1 1
0 0 1 0 1 2 1 9 1 1 0 1
0 1 1 1 1 1 9 1 1 1 1 1

样例输出 #1

59

数据范围与提示

对于 的数据:

  • 数据保证