Luogu 1169 [ZJOI2007]棋盘制作

Description

给一个01矩阵，求出最大的01交错的正方形和最大的01交错的矩阵

Solution

用动态规划求出最大的正方形，用单调栈求出最大的矩阵。

在这里仅介绍求出最大正方形（求最大矩阵 = 单调栈裸题传送门：不会单调栈的同学可以去学

定义数组$f[ i ][ j ]$ 为以$(i, j) $为右下角的正方形的边长

$up[ i ][ j ]$ 表示从点$(i, j)$往上 $01$交错的长度

$lef[ i ][ j ]$ 表示从点$(i, j)$往右$01$交错的长度

当 $a[ i ][ j ] != a[i - 1][j - 1]$时才可由上一个正方形继续拓展，否则长度 $f[ i ][ j ] = 1$

于是有转移方程：

$f[ i ][ j ] = 1$ $a[ i ][ j ] == a[i - 1][j - 1]$

$f[ i ][ j ] = min(f[ i - 1][ j - 1] + 1, lef[ i ][ j ], up[ i ][ j ])$ $ a[ i ][ j ] != a[i - 1][ j ]$

Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rd read()
 5 #define rep(i,a,b) for(register int i = (a); i <= (b); i++)
 6 #define per(i,a,b) for(register int i = (a); i >= (b); --i)
 7 #define R register
 8 using namespace std;
 9 
10 const int N = 3e3;
11 
12 int n, m, a[N][N], pre[N], nxt[N], h[N], ans2;
13 int lf[N][N], u[N][N], f[N][N], ans1;
14 int st[N], tp;
15 
16 int read() {
17     int X = 0, p = 1; char c = getchar();
18     for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1;
19     for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 +  c - '0';
20     return X * p;
21 }
22 
23 void work(int x) {
24     rep(i, 1, m) pre[i] = 0, nxt[i] = m + 1;
25     rep(i, 1, m)
26         if(a[x][i] != a[x - 1][i]) h[i]++;
27         else h[i] = 1;
28     tp = 0;
29     rep(i, 1, m) {
30         int pr = 0;
31         while(tp) {
32             if(h[st[tp]] >= h[i]) tp--;
33             else {
34                 pr = st[tp]; break;
35             }
36         }
37         pre[i] = pr;
38         st[++tp] = i;
39     }
40     tp = 0;
41     per(i, m, 1) {
42         int nt = m + 1;
43         while(tp) {
44             if(h[st[tp]] >= h[i]) tp--;
45             else {
46                 nt = st[tp]; break;
47             }
48         }
49         nxt[i] = nt;
50         st[++tp] = i;
51     }
52     rep(i, 1, m) {
53         int nt = nxt[i], pr = pre[i];
54         rep(j, i + 1, nt)
55             if(a[x][j] == a[x][j - 1]) {nt = j; break;}
56         per(j, i - 1, pr)
57             if(a[x][j] == a[x][j + 1]) {pr = j; break;}
58         ans2 = max(ans2, (nt - pr - 1) * h[i]);
59     }
60 }
61 
62 int main()
63 {
64     n = rd; m = rd;
65     memset(a, -1, sizeof(a));
66     rep(i, 1, n) rep(j, 1, m) a[i][j] = rd;
67     rep(i, 1, n) rep(j, 1, m) {
68         f[i][j] = 1;
69         if(a[i][j] != a[i][j - 1]) 
70             lf[i][j] = lf[i][j - 1] + 1;
71         else lf[i][j] = 1;
72         if(a[i][j] != a[i - 1][j]) 
73             u[i][j] = u[i - 1][j] + 1;
74         else u[i][j] = 1;
75         if(a[i][j] != a[i - 1][j - 1]) continue;
76         f[i][j] = min(u[i][j], lf[i][j]);
77         f[i][j] = min(f[i - 1][j - 1] + 1, f[i][j]);
78         ans1 = max(ans1, f[i][j]);
79     }
80     printf("%d
", ans1 * ans1);
81     rep(i, 1, n) work(i);
82     printf("%d
", ans2);
83 }

View Code