P1169 [ZJOI2007]棋盘制作 

悬线法

悬线法是一种通用的用于求子矩阵的方法

先对于每个点处理出以该点为基点，

向右可以到最远的点，向左可以到的最远的点

则对于每条横轴，处理出若干条线，再对于各个横轴dp合并

更新表示该点纵向向上可延申长度

状态和状态方程 

状态

为点（i，j）向左延申最远的点

为点（i，j）向右延申最远的点

为该点的线向上延申的最长距离

状态转移方程

题意 

 代码

#include <iostream> #include <cstdio> #include <cctype> #include <algorithm> using namespace std; const int maxn = 2005; class QIO { //快读模板 public: char buf[1 << 21], * p1 = buf, * p2 = buf; int getc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; } int read() { int ret = 0, f = 0; char ch = getc(); while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getc(); } while (isdigit(ch)) { ret = ret * 10 + ch - 48; ch = getc(); } return f ? -ret : ret; } char Buf[1 << 21], out[20]; int P, Size = -1; void flush() { fwrite(Buf, 1, Size + 1, stdout); Size = -1; } void write(int x, char ch) { if (Size > 1 << 20) flush(); if (x < 0) Buf[++Size] = 45, x = -x; do { out[++P] = x % 10 + 48; } while (x /= 10); do { Buf[++Size] = out[P]; } while (--P); Buf[++Size] = ch; } }io; int Left[maxn][maxn], Right[maxn][maxn], up[maxn][maxn], a[maxn][maxn]; int main() { int n, m; n = io.read(); m = io.read(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] = io.read(); Left[i][j] = Right[i][j] = j; //初始化 up[i][j] = 1; } } for (int i = 1; i <= n; i++) //预处理向左延申点 for (int j = 2; j <= m; j++) if (a[i][j] != a[i][j - 1]) Left[i][j] = Left[i][j - 1]; for (int i = 1; i <= n; i++) //预处理向右延申点 for (int j = m - 1; j >= 1; j--) if (a[i][j] != a[i][j + 1]) Right[i][j] = Right[i][j + 1]; int ans1 = 0, ans2 = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (i > 1 && a[i][j] != a[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 r = Right[i][j] - Left[i][j] + 1; int c = min(r, up[i][j]); ans1 = max(ans1, c * c); ans2 = max(ans2, r * up[i][j]); } } printf("%d\n%d\n", ans1, ans2); }