Codeforce 373 D Counting Rectangles is Fun (统计全0子矩阵)-蒲公英云

Codeforce 373 D Counting Rectangles is Fun (统计全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;
}