【ZJOI2007】棋盘制作
Description
给定一个01矩阵，求出最大的正方形子矩阵和最大长方形子矩阵，并保证取出的矩阵中的元素都为0/1
Solution
为了使题目变成上述表述的形式，我们首先将读入的矩阵的部分元素xor1，使其变成一般形式
之后，这道题变成了两道题的合体：洛谷P2701巨大的牛棚与P4147玉蟾宫
我们分开讨论，对于最大正方形，我们设计一个dp，定义f[i][j]表示以(i, j)为右下角的最大正方形的边长，状态转移方程为
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1
那么答案也是显然的，ans = max(f[i][j] * f[i][j])
对于最大矩形，我们使用单调栈求解，具体步骤请见这里
注意，本题要求求出最大正方形与矩形，所以我们要将这两个算法对0/1矩阵各做一遍，时间复杂度为O(n^2)
Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int n, m; 6 int a[2010][2010], vis[2010][2010]; 7 int ans1, f1[2010][2010], f2[2010][2010], ans2, b[2010]; 8 int s[2010], p, w[2010]; 9 int main() { 10 scanf("%d%d", &n, &m); 11 for (register int i = 1; i <= m; ++i) vis[1][i] = vis[1][i - 1] ^ 1; 12 for (register int i = 2; i <= n; ++i) 13 for (register int j = 1; j <= m; j++) 14 vis[i][j] = vis[i - 1][j] ^ 1; 15 for (register int i = 1; i <= n; ++i) 16 for (register int j = 1; j <= m; ++j) { 17 scanf("%d", &a[i][j]); 18 if(!vis[i][j]) a[i][j] ^= 1; 19 } 20 for (register int i = 1; i <= n; ++i) 21 for (register int j = 1; j <= m; ++j) 22 if (a[i][j]) { 23 f1[i][j] = min(f1[i - 1][j - 1], min(f1[i - 1][j], f1[i][j - 1])) + 1; 24 ans1 = max(ans1, f1[i][j]); 25 } 26 for (register int i = 1; i <= n; ++i) 27 for (register int j = 1; j <= m; ++j) 28 if (!a[i][j]) { 29 f2[i][j] = min(f2[i - 1][j - 1], min(f2[i - 1][j], f2[i][j - 1])) + 1; 30 ans1 = max(ans1, f2[i][j]); 31 } 32 printf("%d ", ans1 * ans1); 33 for (register int i = 1; i <= n; ++i) { 34 for (register int j = 1; j <= m; ++j) 35 b[j] = a[i][j] ? b[j] + 1 : 0; 36 p = 0; 37 for (register int j = 1; j <= m + 1; ++j) { 38 if (b[j] > s[p]) s[++p] = b[j], w[p] = 1; 39 else { 40 int tot = 0; 41 while (b[j] < s[p]) { 42 tot += w[p]; 43 ans2 = max(ans2, s[p] * tot); 44 p--; 45 } 46 s[++p] = b[j]; 47 w[p] = tot + 1; 48 } 49 } 50 } 51 for (register int i = 1; i <= n; ++i) { 52 for (register int j = 1; j <= m; ++j) 53 b[j] = a[i][j] == 0 ? b[j] + 1 : 0; 54 p = 0; 55 for (register int j = 1; j <= m + 1; ++j) { 56 if (b[j] > s[p]) s[++p] = b[j], w[p] = 1; 57 else { 58 int tot = 0; 59 while (b[j] < s[p]) { 60 tot += w[p]; 61 ans2 = max(ans2, s[p] * tot); 62 p--; 63 } 64 s[++p] = b[j]; 65 w[p] = tot + 1; 66 } 67 } 68 } 69 printf("%d ", ans2); 70 return 0; 71 }