【悬线法】P1169 [ZJOI2007]棋盘制作

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 using std::cin;
 5 using std::cout;
 6 using std::max;
 7 using std::min;
 8 using std::endl;
 9
10 bool c[2010][2010];
11 int n, m;
12 int right[2010][2010], left[2010][2010], up[2010][2010];
13
14 int main()
15 {
16     cin >> n >> m;
17     for (int i = 1; i <= n; i++)
18     {
19         for (int j = 1; j <= m; j++)
20         {
21             cin>> c[i][j];
22
23             left[i][j] = j;
24
25             right[i][j] = j;
26
27             up[i][j] = 1;
28         }
29     }
30     for (int i = 1; i <= n; i++)
31         for (int j = 2; j <= m; j++)
32             if (c[i][j] != c[i][j - 1])
33                 left[i][j] = left[i][j - 1];
34     for (int i = 1; i <= n; i++)
35         for (int j = m - 1; j > 0; j--)
36             if (c[i][j] != c[i][j + 1])
37                 right[i][j] = right[i][j + 1];
38     int maxs1 = -0x3f3f3f3f;
39     int maxs2 = -0x3f3f3f3f;
40     for (int i = 1; i <= n; i++)
41     {
42         for (int j = 1; j <= m; j++)
43         {
44             if (i > 1 && c[i][j] != c[i - 1][j])
45
46             {
47                 left[i][j] = max(left[i][j], left[i - 1][j]);
48
49                 right[i][j] = min(right[i][j], right[i - 1][j]);
50
51                 up[i][j] = up[i - 1][j] + 1;
52             }
53             int a = right[i][j] - left[i][j] + 1;
54             int b = min(a, up[i][j]);
55
56             maxs1 = max(maxs1, b * b);
57
58             maxs2 = max(maxs2, a * up[i][j]);
59
60         }
61     }
62     cout << maxs1 << endl;
63     cout << maxs2;
64 }

View Code