黄金矿工

P2421 - 黄金矿工

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

Sample Output

0

Hint

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

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

首先考虑一维的做法：

设f[i]表示选一个一ｉ为尾的连续的序列，并且是和最大的。

很明显，f[i]=max(s[i]-s[j]),j<=i。

但是这样太慢了，但仔细观察可以发现，这个ｊ其实不需要枚举。

对于每一个ｉ，它只和ｊ有关系，所以就可以在枚举每一个ｉ时看可不可以更新最优的决策，然后就可以Ｏ(n)解决了。

然后推广到二维，可以Ｏ(n^2)枚举列，然后在每一列Ｏ(n)跑个一维的，总复杂度Ｏ（n^3）。

注意要减１０！！！

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<string>
 8 #include<vector>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 #define LL long long
15 #define RG register
16 using namespace std;
17 LL a[310][310],f[310];
18 int main()
19 {
20   freopen("miner.in","r",stdin);
21   freopen("miner.out","w",stdout);
22   int n;
23   LL ans1=0;
24   scanf("%d",&n);
25   for(RG int i=1;i<=n;i++)
26     for(RG int j=1;j<=n;j++){
27       scanf("%lld",&a[i][j]);
28       if(a[i][j]==0) a[i][j]=-1999999999;
29     }
30   for(RG int i=1;i<=n;i++)
31     for(RG int j=1;j<=n;j++)
32       a[i][j]+=a[i][j-1];
33   for(int i=1;i<=n;i++)
34     for(int j=1;j<=n;j++)
35       a[i][j]+=a[i-1][j];
36   for(RG int i=0;i<=n;i++)
37     for(RG int j=i+1;j<=n;j++){
38       memset(f,0,sizeof(f));
39       int po=0;
40       LL ans=0;
41       for(RG int k=1;k<=n;k++){
42     f[k]=(a[k][j]-a[k][i])-(a[po][j]-a[po][i]);
43     if(a[k][j]-a[k][i]<ans) ans=a[k][j]-a[k][i],po=k;
44       }
45       for(int k=1;k<=n;k++)
46     ans1=max(ans1,f[k]);
47     }
48   ans1-=10;
49   if(ans1<0)ans1=0;
50   printf("%lld",ans1);
51   return 0;
52 }