Codeforce 373 D Counting Rectangles is Fun (统计全0子矩阵)

谁借莪１个温暖的怀抱￠ 2022-09-20 15:13 123阅读 0赞

题目链接：http://codeforces.com/contest/373/problem/D

题意:求一个矩阵中有多少个全0子矩阵。

思路：动态规划,dp\[a\]\[b\]\[c\]\[d\]为待求量，矩阵大小只有40\*40，询问数量可以达到3\*10^5，提示应该进行预处理。

状态转移方程:dp\[a\]\[b\]\[c\]\[d\]= dp\[a\]\[b\]\[c-1\]\[d\] + dp\[a\]\[b\]\[c\]\[d-1\] - dp\[a\]\[b\]\[c-1\]\[d-1\]+val

val代表在矩阵(a,b)(c,d)中以(c,d)为右下角的全0矩阵的个数

预处理数组top\[i\]\[j\]表示点(i,j)向上能延伸到最远的0的位置，O(n)向左扫出矩阵的个数。

总体复杂度O(n^5)

#include <cstdio>
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N=42;
    
    int dp[N][N][N][N];
    char g[N][N];
    int top[N][N];
    
    int main()
    {
        int n,m,q,i,j;
        scanf("%d%d%d",&n,&m,&q);
        for (i=1;i<=n;i++)
        {
            scanf("%s",g[i]+1);
            for (j=1;j<=m;j++)
                if (g[i][j]=='0')
                    top[i][j]=top[i-1][j]+1;
                else
                    top[i][j]=0;
        }
        int a,b,c,d;
        for (a=1;a<=n;a++) for (b=1;b<=m;b++)
            for (c=a;c<=n;c++) for (d=b;d<=m;d++)
            {
                dp[a][b][c][d]= dp[a][b][c-1][d] + dp[a][b][c][d-1] - dp[a][b][c-1][d-1];
                int minH = min(top[c][d],c-a+1);
                for (i=d;i>=b;i--)
                {
                    minH = min(top[c][i],minH);
                    if (minH==0) break;
                    else dp[a][b][c][d] += minH;
                }
            }
        while (q--)
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            printf("%d\n",dp[a][b][c][d]);
        }
        return 0;
    }

下面一份代码参考了：http://mochavic.blog.163.com/blog/static/2196651172013111402949522/

利用了部分和的思想，复杂度O(n^4)，但因为循环次数多，所以实际速度没有上面的快

#include <cstdio>
    
    const int N=42;
    int s[N][N];
    char str[N];
    
    int Cal (int x0, int y0, int x1, int y1)
    {
        x0--; y0--;
        return s[x1][y1] - s[x0][y1] - s[x1][y0] + s[x0][y0];
    }
    
    int dp[N][N][N][N];
    int val[N][N][N][N];
    
    int main ()
    {
        int n,m,q,i,j;
        scanf("%d%d%d",&n,&m,&q);
    	for (i=1;i<=n;i++)
        {
            scanf("%s",str);
    		for (j=0;j<m;j++)
                s[i][j + 1] = s[i][j] + str[j] - '0';
        }
    	for (i=1;i<=n;i++)
            for (j=0;j<m;j++)
                s[i][j] += s[i - 1][j];
    //s[i][j]预处理出了(0,0,i,j)范围内所有1的个数
        int x0, x1, y0, y1;
        for (x0 = 1; x0 <= n; x0++)
            for (x1 = x0; x1 <= n; x1++)
                for (y0 = 1; y0 <= m; y0++)
                    for (y1 = y0; y1 <= m; y1++)
                        if (Cal(x0, y0, x1, y1) == 0)
                            val[x0][y0][x1][y1]++;  //(x0,y0,x1,y1)范围内全0
    
    	for (x1 = 1; x1 <= n; x1++)
    		for (y1 = 1; y1 <= m; y1++)
    		{
    			for (i = n; i >= 1; i--)
    				for (j = m; j >= 1; j--)
    					val[i][j - 1][x1][y1] += val[i][j][x1][y1];
    				
    			for (i = n; i >= 1; i--)
    				for (j = m; j >= 1; j--)
                        val[i - 1][j][x1][y1] += val[i][j][x1][y1];
    		}
    //val[x0][y0][x1][y1]为以x1,y1为右下角的左上角不超过x0,y0的全0矩阵个数
        for (x0 = 1; x0 <= n; x0++) for (x1 = x0; x1 <= n; x1++)
    		for (y0 = 1; y0 <= m; y0++) for (y1 = y0; y1 <= m; y1++)
    			dp[x0][x1][y0][y1] = dp[x0][x1 - 1][y0][y1] + dp[x0][x1][y0][y1 - 1] - dp[x0][x1 - 1][y0][y1 - 1] + val[x0][y0][x1][y1];
    
        while (q--)
    	{
            scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
            printf("%d\n", dp[x0][x1][y0][y1]);
        }
        return 0;
    }