1057: [ZJOI2007]棋盘制作

https://www.lydsy.com/JudgeOnline/problem.php?id=1057

分析：

　　首先对于(i+j)&1的位置0->1,1->0，然后就是求一遍最大全1子矩形。然后套用悬线法就可以了。

　　悬线法：处理出每个点向上的最大高度（悬线），然后处理出这条线往左往右的最大距离。　　

　　单调栈好像也可以做。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 inline int read() {
10     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
11     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
12 }
13 
14 const int N = 2010;
15 
16 int h[N][N], L[N][N], R[N][N], a[N][N];
17 int n, m;
18 LL ans1, ans2;
19 
20 LL sqr(int x) {
21     return 1ll * x * x;
22 }
23 void solve(int f) {
24     memset(h, 0, sizeof(h));
25     memset(L, 0, sizeof(L));
26     memset(R, 0x3f, sizeof(R));
27     for (int i=1; i<=n; ++i) {
28         int last = 0;
29         for (int j=1; j<=m; ++j) {
30             if (a[i][j] == f) 
31                 h[i][j] = h[i-1][j] + 1, L[i][j] = max(L[i-1][j], last);
32             else h[i][j] = 0, last = j;
33         }
34         last = m + 1;
35         for (int j=m; j>=1; --j) {
36             if (a[i][j] == f) {
37                 R[i][j] = min(R[i-1][j], last-1); 
38                 ans1 = max(ans1, sqr(min(h[i][j], R[i][j] - L[i][j])));
39                 ans2 = max(ans2, 1ll * h[i][j] * (R[i][j] - L[i][j]));
40             }
41             else last = j;
42         }
43     }
44 }
45 int main() {
46     n = read(), m = read();
47     for (int i=1; i<=n; ++i) {
48         for (int j=1; j<=m; ++j) {
49             a[i][j] = read();
50             if ((i + j) & 1) a[i][j] ^= 1;
51         }
52     }
53     solve(1), solve(0);
54     cout << ans1 << "
" << ans2;
55     return 0;
56 }