王知昆2003年论文首次提出两种解决最大子矩阵问题的方法——一种为O(s^2),另一种为O(nm),其中n,m为矩阵大小,s为障碍点数
注意:下面提到的“悬线法”均为O(nm)的算法,O(s^2)的算法用“另一种悬线法”表示
下面是题单:
洛谷
- P1387 最大正方形:裸的悬线法
- P1169 [ZJOI2007]棋盘制作:裸的悬线法
- P2701 [USACO5.3]巨大的牛棚Big Barn:(不是很确定,可能是悬线法)
- P4147 玉蟾宫:裸的悬线法
- P1578 奶牛浴场:另一种悬线法,普通悬线法过不去
- P3474 [POI2008]KUP-Plot purchase:裸的悬线法,坑点:输入的时候坐标是反的
- P3117 [USACO15JAN]Cow Rectangles G:二分+另一种悬线法
- SP277 CTGAME - City Game:裸的悬线法
- UVA1330 City Game:与SP277重题
- P3331 [ZJOI2011]礼物:悬线法+单调栈?
HDU
- Cut the cake
- To my boyfriend