推 aaaaajack: 最小值的tiebreaker有定好的話(沒定好大概也不會對) 抓 01/18 19:15
→ aaaaajack: 每個2x2的子矩陣就可以了吧 01/18 19:15
定義「單調矩陣」：從上往下看，每一個橫列的最小值，位置往右遞增(非嚴格)。
定義「全單調矩陣」：for all i1 < i2 and j1 < j2
if a[i2][j1] <= a[i2][j2] then a[i1][j1] <= a[i1][j2]
試證：給定一個矩陣，若所有子矩陣都是「單調矩陣」，則是「全單調矩陣」。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.6.195
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1484701852.A.2C3.html
※ 編輯: DJWS (220.137.6.195), 01/18/2017 09:12:36