TIOJ1643-建築工程規劃

題目：http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1643
有一N*M(1000*1000)的棋盤格
畫出面積最大的一塊長方形，滿足長方形內最大值-最小值不超過L(20)


程式碼：http://codepad.org/88C4FPb2
被一串室友戳倒的題目，隔了快10天突然想出來
整個解題的思路是這樣的，這兒有三個問題：

A.改編傳統最大長方形，一次算出L=0的情形
B.改編傳統最大長方形，在可接受的次數內算出L=1的情形
C.試著把B的結果推廣，理想上使用與L成正比的次數解出本題

首先問題A其實相當好辦
(你也許會先想像充滿0/1的矩陣，要框一塊裡面全0或全1)
只要在傳統最大長方形進行push/pop的時候，多考慮一個像是「顏色」的因素
也就是說，stack內的元素除了原本就滿足「高度由小到大」、又多了「顏色全部一樣」
如此掃一遍就能求出來了


我在B遇到相當的瓶頸，設若有1,2,3,4,5五種元素
那麼就有[1,2][2,3][3,4][4,5]四種不同的定色方法
而且[1,2][2,3]還會交纏在一起，然後腦袋就跟著纏在一起了(誤)
(方便描述起見，我們設定G=N*M)
假如這四種全部做的話
將意味我們掃的次數會和G成正比
有多少不同的數字就得做多少遍，肯定炸

當L=1的時候，有機巧可循：先做奇數類再做偶數類
錯開的部分可以一併解決
也就是說先把[1,2][3,4]這兩種各染一個顏色做一次、[2,3][4,5]再染一次
這樣L=1的時候只要做兩次，舒服多了


再來問題C就是整題最神奇的地方
(請參考程式碼112行【//*magic cycle】的部分)
這個「能染色就盡量染色」的迴圈，每執行一次要花GlgG的時間(要二分搜定色)
我說這個迴圈再怎麼樣也不會執行超過21次(也就是L+1次)
為什麼呢？
試想當你將[x,x+5]這個區間染成一個顏色的時候會犧牲哪些可能性沒找呢？
那些被纏住沒辦法同時做的區間是[x+1,x+6] [x+2,x+7] [x+3,x+8] [x+4,x+9] [x+5,x+10]
從這個最壞的情形可以確知，L=5的時候最多用六種染色方案可以含括全部可能性

總時間複雜度O(GlgGL)..................我的程式跑了6.5秒(死)