关于黄金矿工的近10条评论(全部评论)
按理来说这个算法是有漏洞的，当法f[i][j]与f[k][j]都是0会有错。。。 ps：细节真是坑 mikumikumi 2015-04-12 17:09 7楼
Mark 马克 HouJikan 2014-05-16 23:08 6楼
暑假B班的时候见了一道三维的。逐维慢慢的优化（降维）。当时原本是道枚举题。超级傲娇的AC酱 2014-01-08 13:37 5楼
抄袭蛋蛋神的题解 http://www.wyfenger.tk/2012-10-31/COGS/miner feng 2012-10-31 10:15 4楼
绝对值<100，一共300X300，最大绝对值9000000，设为10000000，把该值设为TNT绝对值那么最大绝对值10000000，一共300X300，即使全部占满TNT，然后求和，int不会爆预处理+枚举+DP【O(n^3)】预处理：s[i][j]-->第j列前i行和。枚举：开始行和结束行（error for two times） DP：和一维的求连续最大和一样。 Truth.Cirno 2012-10-31 07:44 3楼
这题咋又不会做？还在纠结于这道题？还在为这道题而烦恼？还不快上http://paulinsider.at.ua/news/tyvj_aug11/2012-10-30-19上看题解，快，稳，准，神牛，大犇的选择！苏轼 2012-10-30 17:28 2楼
此処（ここ）は官方题解です。 Makazeu 2012-10-30 16:08 1楼

822. [Tyvj Aug11] 黄金矿工

★ 输入文件：miner.in 输出文件：miner.out 简单对比
时间限制：1 s 内存限制：128 MiB

来源：TYVJ八月月赛提高组第3题

描述 Description
	黄金矿工是一个经典的小游戏，它可以锻炼人的反应能力。该游戏中，可以通过“挖矿”获得积分并不断升级。玩家可以在线玩flash版黄金矿工，也可以下载后玩单机版黄金矿工。目前，黄金矿工小游戏有多个版本，例如黄金矿工双人版，黄金矿工单人版等。 Jimmy是一位黄金矿工，他所在的金矿是一个nn的矩形区域（俯视），区域内有黄金、石头和TNT，由一个nn的矩阵描述。黄金的价值对应矩阵中的正值，石头的价值对应矩阵中的负值，TNT由0表示。换句话说，挖到黄金赚钱，石头亏损，如果挖到TNT就挂了~_~ Jimmy租到的挖矿工具很特别，它的形状是一个长宽任意（均为正整数）的矩形，可以取走被该工具覆盖的矩形区域内的所有物品，但如果该区域内有TNT，该工具将被炸毁，此时Jimmy将不得不赔偿矿主+∞元！！！需要注意的是，该工具只能在金矿范围内使用（即不得超出金矿边界），且租金为每次使用十元。现在，Jimmy想知道，如果他至多只有一次租用该工具的机会，他能获得的最大收益是多少。当然，如果Jimmy租用该工具无论如何都会亏损，他可以不租用，此时收益为0.

输入格式 Input Format
	第一行：一个整数n 接下来n行，每行n个整数（绝对值<100），为题目中所描述的矩阵。

输出格式 Output Format
	一个数，即Jimmy所能获得的最大收益。

样例输入 Sample Input

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

样例输出 Sample Output

数据范围和注释 Hint

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

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