聪明的矿工
时间: 1ms 内存:128M
描述:
小陈不好好学习,毕业之后为了生计,不得去矿场挖矿(真惨),小陈实地考察了下矿场,发现矿场是一个N*N大小的方形矿场(1<=N<=500),并且每个矿石都有一个价值,但是矿场内部也会有硫酸会腐蚀矿石,假设矿石价值为10,硫酸腐蚀是7,那么这两个一结合,矿石价值就只剩3.矿场有规定,必须是选择一个矩形大小的矿地挖掘,而且必须全挖掘完毕(不能只要矿石,而不要硫酸),假设小陈可以挖掘任意矩形大小的矿地,请问小陈从这片矿地最大可以获得多少利润,当然小陈不能做亏本的买卖哈。
输入:
先输入N,表示矿场的大小,之后输入N行N列的数字,代表矿场中每一个部分的价值,正数代表矿石的价值,负数代表硫酸腐蚀矿石的能力。矿石价值大小是[0,10]之间,硫酸腐蚀能力大小是[-10,0]之间。
输出:
小陈可以获得的最大利润X。
示例输入:
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
示例输出:
15
提示:
参考答案:
解锁文章
文章评论