例题 P1169

齐线法是动态规划中的一个重要的方法，可以计算出符合要求的最大子矩形。其核心思路为：维护三个数组$l[i][j],r[i][j],h[i][j]$，分别表示在$(i,j)$处可以扩展到的最左边界、最右边界、最大高度，然后通过这三个数组进行动规。

转移方程如下：$$l[i][j]=l[i][j-1]\,(\text{满足条件时})$$$$r[i][j]=r[i][j+1]\,(\text{满足条件时})$$$$h[i][j]=h[i-1][j]+1\,(\text{满足条件时})$$ 完成转移之后，便可根据题意求出对应的矩形。

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2010;
int clr[MAXN][MAXN], l[MAXN][MAXN], r[MAXN][MAXN], h[MAXN][MAXN];
int n, m, ans1, ans2;

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= n; i++) 
        for(register int j = 1; j <= m; j++) {
            scanf("%d", &clr[i][j]);
            l[i][j] = r[i][j] = j;
            h[i][j] = 1;
        }
    for(register int i = 1; i <= n; i++)
        for(register int j = 2; j <= m; j++)
            if(clr[i][j] != clr[i][j - 1])
                l[i][j] = l[i][j-1];
    for(register int i = 1; i <= n; i++)
        for(register int j = m - 1; j >= 1; j--)
            if(clr[i][j] != clr[i][j + 1])
                r[i][j] = r[i][j + 1];
    // 预处理左右边界
    for(register int i = 1; i <= n; i++)
        for(register int j = 1; j <= m; j++) {
            if(i > 1 && clr[i][j] != clr[i - 1][j]) {
                l[i][j] = max(l[i][j], l[i - 1][j]);
                r[i][j] = min(r[i][j], r[i - 1][j]);
                h[i][j] = h[i - 1][j] + 1;
            }
            int width = r[i][j] - l[i][j] + 1;
            int len = min(width, h[i][j]);
            ans1 = max(ans1, len * len);
            ans2 = max(ans2, width * h[i][j]);
        }
    printf("%d\n%d", ans1, ans2);
    return 0;
}