傳送門

Description

黃金礦工是一個經(jīng)典的小游戲，它可以鍛煉人的反應(yīng)能力。該游戲中，可以通過“挖礦”獲得積分并不斷升級。玩家可以在線玩flash版黃金礦工，也可以下載后玩單機(jī)版黃金礦工。目前，黃金礦工小游戲有多個版本，例如黃金礦工雙人版，黃金礦工單人版等。

Jimmy是一位黃金礦工，他所在的金礦是一個n*n的矩形區(qū)域（俯視），區(qū)域內(nèi)有黃金、石頭和TNT，由一個 n*n的矩陣描述。黃金的價值對應(yīng)矩陣中的正值，石頭的價值對應(yīng)矩陣中的負(fù)值，TNT由0表示。換句話說，挖到黃金賺錢，石頭虧損，如果挖到TNT就掛了。

Jimmy租到的挖礦工具很特別，它的形狀是一個長寬任意（均為正整數(shù)）的矩形，可以取走被該工具覆蓋的矩形區(qū)域內(nèi)的所有物品，但如果該區(qū)域內(nèi)有TNT，該工具將被炸毀，此時Jimmy將不得不賠償?shù)V主+∞元！！！需要注意的是，該工具只能在金礦范圍內(nèi)使用（即不得超出金礦邊界），且租金為每次使用十元。

現(xiàn)在，Jimmy想知道，如果他至多只有一次租用該工具的機(jī)會，他能獲得的最大收益是多少。當(dāng)然，如果Jimmy租用該工具無論如何都會虧損，他可以不租用，此時收益為0.

Input

第一行：一個整數(shù)n
接下來n行，每行n個整數(shù)（絕對值<100），為題目中所描述的矩陣。

Output

一個數(shù)，即Jimmy所能獲得的最大收益。

Sample Input

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

Sample Output

0

Hint

【樣例解釋】
無論Jimmy怎么挖礦，挖到的不是石頭，就是TNT，總之無論如何都會虧損，所以選擇不租用工具，收益為0

【數(shù)據(jù)范圍】
對于30%的數(shù)據(jù)：0＜n<=10
對于60%的數(shù)據(jù)：0＜n<=100
對于100%的數(shù)據(jù)：0＜n<=300

Source

動態(tài)規(guī)劃， 貪心，子矩陣DP

?

?

這是一道很好的DP題，首先這道題的模型就是求最大子矩陣和。很容易想到的暴力枚舉是O（n^4）的,顯然會TLE，我們發(fā)現(xiàn)，暴力枚舉的時候我們很多東西都重復(fù)計算了，沒有很好的利用中間結(jié)果。

首先從一維的子序列最大和講起。對于任意數(shù)列，O（n）的求它最大的子序列和，設(shè)f[i]表示到i位置的最大和，那么狀態(tài)的轉(zhuǎn)移只有兩種，如果f[i-1]>0，那么 f[i]=f[i-1]+a[i]，否則f[i]=a[i]。因為要求最大的子序列和，所以所選的子序列的起始位置一定是正數(shù)。

當(dāng)f[i]>0時，這個轉(zhuǎn)移顯然是對的，（每次轉(zhuǎn)移后都會更新答案，所以a[i]<0也不會影響答案）

當(dāng)f[i-1]<0時，f[i-1]+a[i]一定小于 a[i]，而i-1是從上一個起始位置開始，一段子序列中和第一次小于0的位置，同時序列的起點又是正數(shù)，所以上一次選的序列中不存在一個位置到當(dāng)前位置的序列和大于0，所以新序列從 i 位置開始。

然后類比到二維的子矩陣和，我們可以把一個矩形一列的和看做一維數(shù)組的一個元素，轉(zhuǎn)化為上面那個問題，這樣就只需枚舉矩形的上下界，求和的話可以用前綴和優(yōu)化，記錄每一列的前綴和，這樣就可以O(shè)（1）求矩形一列的和。總復(fù)雜度為O（n^3）。

還可以參見這篇博客，博主講得很清楚。

?

?

1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 #define ll long long 16 17 inline int gi() 18 { 19 bool b=0; int r=0; char c=getchar(); 20 while(c<'0' || c>'9') { if(c=='-') b=!b; c=getchar(); } 21 while(c>='0' && c<='9') { r=r*10+c-'0'; c=getchar(); } 22 if(b) return -r; return r; 23 } 24 25 const int inf = 21400000, N = 307; 26 int a[N][N]; 27 28 int main() 29 { 30 int i,j,k,sum,ans,n; 31 n=gi(); 32 for (i=1; i<=n; i++) 33 for (j=1; j<=n; j++) 34 { 35 a[i][j]=gi(); 36 if (!a[i][j]) a[i][j]=-inf; 37 a[i][j]+=a[i-1][j]; //記錄每一列的前綴和 38 } 39 for (i=1; i<=n; i++) //枚舉子矩形下面邊的位置 40 for (k=0; k<i; k++) //枚舉子矩形上面邊的位置 41 { 42 sum=0; 43 for (j=1; j<=n; j++) //枚舉矩形的寬 若 sum 大于 0 則繼續(xù)擴(kuò)展 每次更新 ans 否則 sum=0 重新枚舉一個子矩形 妙不可言 44 { 45 sum+=a[i][j]-a[k][j]; 46 if (sum < 0) sum=0; 47 else ans=max(ans,sum); 48 } 49 } 50 printf("%d\n",max(ans-10,0)); 51 return 0; 52 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/y142857/p/7152992.html

總結(jié)

以上是生活随笔為你收集整理的[Tyvj Aug11] 黄金矿工的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。