创意吃鱼法

发表于 更新于 分类于

Problem’s Website

  • 创意吃鱼法

    Solution

  • 这道题类似于[USACO5.3]巨大的牛棚Big Barn，这道题要求出子矩阵中1组成的最长的对角线长度，我们回想一下巨大的牛棚是如何AC的，那道题我们设f[i][j]为以i,j为右下角的最大正方形边长，状态转移方程为

    1
    2
    if(!Map[i][j])
    	f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1]));

    这道题我们可以设f[i][j]为以i,j为右下角的正方形1组成最大对角线的长度，对于f[i][j]，我们肯定要和f[i - 1][j - 1]比较，同时，既然是1组成的对角线，我们可以记录两个数组分别存从i,j向上下、左右一直为0的长度，我们就可以与这两个数组相比，状态转移方程为

    1
    2
    if(Map[i][j])
    	f[i][j] = min(f[i - 1][j - 1], min(s1[i][j - 1], s2[i - 1][j]));

    当然这道题遍历两遍，一遍从左上角到右下角，一遍从右上角到左下角，状态转移方程稍有不同，请读者自行查看Code

    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
    #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, ans;
    int Map[2510][2510], f[2510][2510], s1[2510][2510], s2[2510][2510];
    int main() {
    	n = sc(); m = sc();
    	for(int i = 1; i <= n; i++){
    		for(int j = 1; j <= m; j++) {
    			Map[i][j] = sc();
    			if(!Map[i][j]) {
    				s1[i][j] = s1[i][j - 1] + 1;
    				s2[i][j] = s2[i - 1][j] + 1;
    			}
    			if(Map[i][j]) f[i][j] = min(f[i - 1][j - 1], min(s2[i - 1][j], s1[i][j - 1])) + 1;
    			ans = max(ans, f[i][j]);
    		}
    	}
    	memset(s1, 0, sizeof(s1));
    	memset(s2, 0, sizeof(s2));
    	memset(f, 0, sizeof(f));
    	for(int i = 1; i <= n; i++) {
    		for(int j = m; j >= 1; j--) {
    			if(!Map[i][j]){
    				s1[i][j] = s1[i][j + 1] + 1;
    				s2[i][j] = s2[i - 1][j] + 1;
    			}
    			if(Map[i][j]) f[i][j] = min(f[i - 1][j + 1], min(s1[i][j + 1], s2[i - 1][j])) + 1;
    			ans = max(ans, f[i][j]);
    		}
    	}
    	printf("%d\n", ans);
    	return 0;
    }

rp++\