HOJ90-買賣土地

題目：http://hoj.mooo.com/judge/index.php/problem/view/90
給一個N*N大小(N<=2000)的矩陣以及K值，問是否存在一個子矩陣和t滿足K<=t<=2K



程式碼放到桌電去了QQ
畢竟是土地價錢應該不會有負的吧？
(還好後來問好威證傑確定都是正的，不然我下面的證明就白搭了:[)
首先會發現對數字都很random很多的情況幾乎都會有解
而且會有非常多組解...
心想要如何構造一個無解的測資呢？
這個原則就是"讓大的數字很大加了會爆，讓小的數字很小加了會不夠"

於是很自然的想到對矩陣內的元素討論：
1.大於2k的元素，顯然怎麼加都沒答案，是必須避開的
2.剛好介於k到2k的元素本身就是答案
3.小於k的元素

也就是只剩下"胖的元素"和"瘦的元素"

這時候不禁要問，瘦的元素是不是越多、越大越容易得到答案呢？
思考良久加上經過多方揣測之後
得出下面這個關鍵性的結論

「由小於k的元素構成的矩陣總和T若大於2k，必定存在一子矩陣和T'滿足k<=T'<=2k」

證明：
(1)該矩陣的元素各數必定>=3
設元素是x，則一個x<k、或兩個2x<2k都不行，三個3x<3k才有可能3x>2k

(2).承1這個矩陣必定可以拆解
我們將這個矩陣任意切成兩個部分，令它們總和小的那塊是p、大的那塊是q
分以下各種情況討論
[A]p<k , q<k和原命題p+q>2k矛盾
[B]p<k , k<=q<=2k得到答案
[C]p<k , q>2k則由於(1)保證q有兩個以上元素可以繼續拆解
[D]k<=p<=2k得到答案
[E]p>2k , q>2k同C，隨便拿一塊去拆

總結(1)(2)，每次拆解都必定有[得到答案]或是[可以繼續拆解]這兩種結果，證畢



好的，寫到這裡要怎麼設計算法呢？
於是很容易聯想到一個基礎問題的描述是這樣的：
在二維平面上有很多黑或白的格子，劃出最大的長方形區域讓區域裡面全部是白格子
(即最大空長方形問題)

順水推舟、風調雨順、水到渠成、肥水不落外人田(?)

把全部元素讀進來，
遇到解答直接輸出、大於2k當黑格子，從小於k元素(白格子)找一個總和大於2k的區域
然後隨便亂拆(我是定出w、h，把大的那一個對半切)就有答案了

.
.
.
.
.
分析至此才愕然發現原來我不會寫最大空長方形...(掩面哭泣逃走)