算法训练 采油区域
时间限制:2.0s 内存限制:512.0MB
采油区域 Siruseri 政府决定将石油资源丰富的 Navalur 省的土地拍卖
给私人承包商以建立油井。被拍卖的整块土地为一个矩形区域,被划分为
M
×
N
个小块。
Siruseri 地质调查局有关于 Navalur 土地石油储量的估测数据。这些数据
表示为
M
×
N
个非负整数,即对每一小块土地石油储量的估计值。
为了避免出现垄断,政府规定每一个承包商只能承包一个由
K
×
K
块相连的
土地构成的正方形区域。
AoE 石油联合公司由三个承包商组成,他们想选择三块互不相交的
K
×
K
的
区域使得总的收益最大。
例如,假设石油储量的估计值如下:
如果
K
= 2, AoE 公司可以承包的区域的石油储量总和为 100, 如果
K
= 3,
AoE 公司可以承包的区域的石油储量总和为 208。
AoE 公司雇佣你来写一个程序,帮助计算出他们可以承包的区域的石油储量
之和的最大值。
输入格式
输入第一行包含三个整数
M
,
N
,
K
,其中
M
和
N
是矩形区域的行数和列数,
K
是每一个承包商承包的正方形的大小(边长的块数)。接下来
M
行,每行有
N
个非负整数表示这一行每一小块土地的石油储量的估计值。
输出格式
评论0