一、悬线法
原作者博客 https://rpdreamer.blog.luogu.org/p1169
#include <bits/stdc++.h> using namespace std; namespace fdata { inline char nextchar() { static const int BS = 1 << 21; static char buf[BS], *st, *ed; if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin); return st == ed ? -1 : *st++; } inline int poread() { int ret = 0; char ch; while (!isdigit(ch = nextchar())) ; do ret = ret * 10 + ch - '0'; while (isdigit(ch = nextchar())); return ret; } } // namespace fdata using fdata::poread; const int MAXN = 2005; int res[MAXN][MAXN], left_[MAXN][MAXN], right_[MAXN][MAXN], up_[MAXN][MAXN]; int n, m, ans1, ans2; int main() { #ifdef lky233 system("color FD"); freopen("testdata.in", "r", stdin); freopen("testdata.out", "w", stdout); #endif n = poread(); m = poread(); for (register int i = 1; i <= n; ++i) { for (register int j = 1; j <= m; ++j) { res[i][j] = poread(); left_[i][j] = right_[i][j] = j; up_[i][j] = 1; } } for (register int i = 1; i <= n; ++i) for (register int j = 2; j <= m; ++j) { if (res[i][j] != res[i][j - 1]) left_[i][j] = left_[i][j - 1]; } for (register int i = 1; i <= n; ++i) for (register int j = m - 1; j > 0; --j) if (res[i][j] != res[i][j + 1]) right_[i][j] = right_[i][j + 1]; for (register int i = 1; i <= n; ++i) for (register int j = 1; j <= m; ++j) { if (i > 1 && res[i][j] != res[i - 1][j]) { left_[i][j] = max(left_[i][j], left_[i - 1][j]); right_[i][j] = min(right_[i][j], right_[i - 1][j]); up_[i][j] = up_[i - 1][j] + 1; } int a = right_[i][j] - left_[i][j] + 1; int b = min(a, up_[i][j]); ans1 = max(ans1, b * b); ans2 = max(ans2, a * up_[i][j]); } printf("%d %d", ans1, ans2); }
思路：预处理左右边界然后计算长度。
二、单调栈
#include <bits/stdc++.h> using namespace std; namespace fdata { inline char nextchar() { static const int BS = 1 << 21; static char buf[BS], *st, *ed; if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin); return st == ed ? -1 : *st++; } inline int poread() { int ret = 0; char ch; while (!isdigit(ch = nextchar())) ; do ret = ret * 10 + ch - '0'; while (isdigit(ch = nextchar())); return ret; } } // namespace fdata using fdata::poread; const int MAXN = 2005; int n, m, top, cur, ans1, ans2; int stack[MAXN], map[MAXN][MAXN], h[MAXN]; int main() { #ifdef lky233 system("color FD"); freopen("testdata.in", "r", stdin); freopen("testdata.out", "w", stdout); #endif n = poread(); m = poread(); for (register int i = 1; i <= n; ++i) for (register int j = 1; j <= m; ++j) ::map[i][j] = poread(); for (register int j = 1; j <= n; ++j) { for (register int i = 1; i <= m; ++i) if (j > 1 && ::map[j][i] != ::map[j - 1][i]) ++h[i]; else h[i] = 1; cur = 1; while (cur <= m) { ::stack[0] = cur - 1; ::stack[top = 1] = cur++; while (cur <= m && ::map[j][cur] != ::map[j][cur - 1]) { while (top && h[::stack[top]] > h[cur]) { int x = h[::stack[top]]; int y = cur - ::stack[top - 1] - 1; int z = min(x, y); ans1 = max(ans1, z * z), ans2 = max(ans2, x * y), --top; } ::stack[++top] = cur++; } while (top) { int x = h[::stack[top]]; int y = cur - ::stack[top - 1] - 1; int z = min(x, y); ans1 = max(ans1, z * z); ans2 = max(ans2, x * y); --top; } } } printf("%d %d ", ans1, ans2); return 0; }