[问题] 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