[問題] totally monotone matrix

作者: DJWS (...)   2017-01-18 09:10:48
定義「單調矩陣」:從上往下看,每一個橫列的最小值,位置往右遞增(非嚴格)。
定義「全單調矩陣」:for all i1 < i2 and j1 < j2
if a[i2][j1] <= a[i2][j2] then a[i1][j1] <= a[i1][j2]
試證:給定一個矩陣,若所有子矩陣都是「單調矩陣」,則是「全單調矩陣」。
作者: aaaaajack (丁丁是個人才)   2017-01-18 19:15:00
最小值的tiebreaker有定好的話(沒定好大概也不會對) 抓每個2x2的子矩陣就可以了吧

Links booklink

Contact Us: admin [ a t ] ucptt.com