棋盘制作

发表于 更新于 分类于

Problem’s Website

  • [ZJOI2007]棋盘制作

    Solution

  • 又是一个求最大矩阵和正方形的问题，方法还是dp，有个专有名词——悬线法，最普通的状态转移方程为

    1
    f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1]));

    而这道题要满足是一个棋盘，我们可以设Left[i][j]为i，j能到达的最左位置，Right[i][j]为i,j能到达的最右位置，up[i][j]为i,j能向上延伸的最大长度，状态转移方程为

    1
    2
    Left[i][j] = max(Left[i][j], Left[i - 1][j]);
    Right[i][j] = min(Right[i][j], Rigth[i - 1][j]);

    具体解释见代码。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    using namespace std;
    int sc() {
    	int xx = 0, ff = 1; char cch = gc;
    	while(cch < '0' || cch > '9') {
    		if(cch == '-') ff = -1; cch = gc;
    	}
    	while(cch >= '0' && cch <= '9') {
    		xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    	}
    	return xx * ff;
    }
    int n, m, ans1, ans2;
    int Left[2010][2010], Right[2010][2010], up[2010][2010], Map[2010][2010];
    int main() {
    	n = sc(); m = sc();
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= m; j++) {
    			Map[i][j] = sc();
    			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(Map[i][j] != Map[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(Map[i][j] != Map[i][j + 1])
    				Right[i][j] = Right[i][j + 1];
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= m; j++) {
    			if(i > 1 && Map[i][j] != Map[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 a = Right[i][j] - Left[i][j] + 1;
    			int b = min(a, up[i][j]);
    			ans1 = max(ans1, b * b); //最大正方形面积 
    			ans2 = max(ans2, a * up[i][j]); //最大矩形面积 
    		}
    	}
    	printf("%d\n%d\n", ans1, ans2);
    	return 0;
    }

rp++