首页 > 代码库 > [Tyvj Aug11] 黄金矿工

[Tyvj Aug11] 黄金矿工

传送门

Description

黄金矿工是一个经典的小游戏,它可以锻炼人的反应能力。该游戏中,可以通过“挖矿”获得积分并不断升级。玩家可以在线玩flash版黄金矿工,也可以下载后玩单机版黄金矿工。目前,黄金矿工小游戏有多个版本,例如黄金矿工双人版,黄金矿工单人版等。

Jimmy是一位黄金矿工,他所在的金矿是一个n*n的矩形区域(俯视),区域内有黄金、石头和TNT,由一个 n*n的矩阵描述。黄金的价值对应矩阵中的正值,石头的价值对应矩阵中的负值,TNT由0表示。换句话说,挖到黄金赚钱,石头亏损,如果挖到TNT就挂了。

Jimmy租到的挖矿工具很特别,它的形状是一个长宽任意(均为正整数)的矩形,可以取走被该工具覆盖的矩形区域内的所有物品,但如果该区域内有TNT,该工具将被炸毁,此时Jimmy将不得不赔偿矿主+∞元!!!需要注意的是,该工具只能在金矿范围内使用(即不得超出金矿边界),且租金为每次使用十元。

现在,Jimmy想知道,如果他至多只有一次租用该工具的机会,他能获得的最大收益是多少。当然,如果Jimmy租用该工具无论如何都会亏损,他可以不租用,此时收益为0.

Input

第一行:一个整数n
接下来n行,每行n个整数(绝对值<100),为题目中所描述的矩阵。

Output

一个数,即Jimmy所能获得的最大收益。

Sample Input

3
0 -1 -1
0 -12 0
-19 0 0

Sample Output

0

Hint

【样例解释】
无论Jimmy怎么挖矿,挖到的不是石头,就是TNT,总之无论如何都会亏损,所以选择不租用工具,收益为0

【数据范围】
对于30%的数据:0<n<=10
对于60%的数据:0<n<=100
对于100%的数据:0<n<=300

Source

动态规划, 贪心,子矩阵DP

 

 

[Tyvj Aug11] 黄金矿工