POJ 1050 To the Max 解題報(bào)告

     摘要: POJ 2479/POJ 2593的拓展，從一維數(shù)組變成了二維矩陣，不過我們可以把情況模擬成一維的情況，在DP的基礎(chǔ)上需要加上枚舉。
題目要求求出給定的一個(gè)矩陣的和最大的子矩陣。
我們可以枚舉第a行到第c行的情況（假設(shè)已經(jīng)確定矩陣已經(jīng)確定為最上面為第a行，最下面為第c行），那么只需要確定列的范圍即可。我們可以把每一列都求和，這樣會(huì)得到單獨(dú)的一行，就可以直接求這一行的最大子段和即可。  閱讀全文

posted @ 2011-11-27 17:29 LoveBeyond| 編輯 收藏