其实是 3.4 那天的模拟赛，那天打的挺崩溃来着，但是后来停电了（就很乐），于是比赛没打完，然后一直没来电就提前放学了捏。今天重赛了，来写写。
T1 P1169 [ZJOI2007]棋盘制作 传送门
参考了洛谷大佬的题解。tql。
思路：找到符合 0101 这样的最大长方形和正方形。垂线法 dp：记录每个格子 (i, j) 最右端的障碍点、最左端的障碍点、上下能拓展的长度，即垂线标注，分别用 l[i][j],r[i][j],up[i][j] 表示。
1.初始化：从列的角度根据之前的分别初始记录障碍点，注意边界。
2.一边计算一边更新：从行的角度根据之前的分别更新障碍点。up 向下拓展。
方程 : l[i][j] = max(l[i][j], l[i - 1][j]), r[i][j] = min(r[i][j], r[i - 1][j]), up[i][j] = up[i - 1][j] + 1。
至于为什么是 max l 和 min r，可以画图理解，这个就是之前在列处理时，有的地方并没有考虑到行的状态，所以更新准确的障碍点位置。
3.一些脑残的小问题捏：注意区分长和宽；特别注意最后输出时是换行还是空格，有的 sb 题（例如本题）会卡，还是严谨一些好。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N = 2010;
4 int n, m;
5 int x, y, ans1 = 0, ans2 = 0;
6 int a[N][N], l[N][N], r[N][N], up[N][N];
7 int main()
8 {
9 scanf("%d%d", &n, &m);
10 for(int i = 1; i <= n; i ++ )
11 for(int j = 1; j <= m; j ++ )
12 {
13 scanf("%d", &a[i][j]);
14 l[i][j] = r[i][j] = j;
15 up[i][j] = 1;
16 }
17 for(int i = 1; i <= n; i ++ )
18 for(int j = 2; j <= m; j ++ )
19 if(a[i][j] != a[i][j - 1])
20 l[i][j] = l[i][j - 1];
21 for(int i = 1; i <= n; i ++ )
22 for(int j = m - 1; j >= 1; j -- )
23 if(a[i][j] != a[i][j + 1])
24 r[i][j] = r[i][j + 1];
25 for(int i = 1; i <= n; i ++ )
26 for(int j = 1; j <= m; j ++ )
27 {
28 if(i > 1 && a[i][j] != a[i - 1][j])
29 {
30 l[i][j] = max(l[i][j], l[i - 1][j]);
31 r[i][j] = min(r[i][j], r[i - 1][j]);
32 up[i][j] = up[i - 1][j] + 1;
33 }
34 x = r[i][j] - l[i][j] + 1;
35 y = min(up[i][j], x);
36 ans1 = max(ans1, y * y);
37 ans2 = max(ans2, x * up[i][j]);
38 }
39 printf("%d\n%d", ans1, ans2);
40 return 0;
41 }
luogu P1169 棋盘制作
T2 bzoj 2086 Blocks
由于 bzoj 好像很久之前就寄了，所以这里光放一下题面捏。
本题正解：dp + 单调栈（甚至不算 dp ）。
思路：
标签：min,int,ans1,ans2,up,2023.3,max From： https://www.cnblogs.com/Moyyer-my/p/17189661.html