p4147专题

动态规划——悬线法 (P1169 棋盘制作 p4147 玉蟾宫 p2701 巨大的牛棚 p1387 最大正方形)

学习于luogu p1169 第一篇题解 悬线法 用途:        解决给定矩阵中满足各种条件的最大子矩阵 做法:   用一条线(横竖貌似都行)左右移动直到不满足约束条件或者到达边界 定义数组:   le[i][j]: 代表从(i,j)能到达的最左位置   ri[i][j]: 代表从(i,j)能到达的最右位置   up[i][j]: 代表从(i,j)向上扩展最长长度. 预处