5-14补题 第九次训练

动态规划 第九次训练 dp综合

C Counting Rectangles is Fun

题意：给定一个nm的01矩阵，q次询问，每次询问为4个整数a,b,c,d，输出以左上顶点为(a,b)，右下顶点为(c,d)的矩阵内的“好矩阵”的个数。
好矩阵：只包含0的矩阵。

用四元组(a,b,c,d)来表示一个矩阵。
二维dp，设
dp1[a][b][c][d]表示(a,b,c,d)这个矩阵以(c,d)为右下顶点的“好矩形”个数
dp2[a][b][c][d]表示(a,b,c,d)这个矩阵内的“好矩形”个数
row[i][j]表示以(i,j)结尾的形状为1*m的“好矩形”个数
col[i][j]表示以(i,j)结尾的形状为m*1的“好矩形”个数

状态转移方程
dp1[a][b][c][d] = dp1[max(a,c-col[c][d]+1)][max(b,d-row[c][d]+1)][c-1][d-1] + min(col[c][d], c-a+1) + min(row[c][d], d-b+1) - 1;
dp2[a][b][c][d] = dp2[a][b][c][d-1] + dp2[a][b][c-1][d] - dp2[a][b][c-1][d-1] + dp1[a][b][c][d];
时间复杂度O(n^2m^2+q)
（总觉得这题我做的麻烦了，网上看了别的代码都挺简单，，

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, q;
char s[50][50];
int row[50][50], col[50][50];
int dp1[50][50][50][50];
int dp2[50][50][50][50];
void init();
int main(){
    scanf ("%d %d %d", &n, &m, &q);
    for (int i=1;i<=n;i++)  scanf ("%s", s[i]+1);
    init();
    while (q--){
        int a, b, c, d;
        scanf ("%d %d %d %d", &a, &b, &c, &d);
        printf ("%d\n", dp2[a][b][c][d]);
    }
    return 0;
}

void init(){
    for (int i=1;i<=n;i++){
        if (s[i][1]=='0')    row[i][1] = 1;
        for (int j=2;j<=m;j++)
            if (s[i][j]=='0')
                row[i][j] = row[i][j-1] + 1;
    }
    for (int j=1;j<=m;j++){
        if (s[1][j]=='0')    col[1][j] = 1;
        for (int i=2;i<=n;i++)
            if (s[i][j]=='0')
                col[i][j] = col[i-1][j] + 1;
    }
    for (int a=n;a>=1;a--){
        for (int b=m;b>=1;b--){
            for (int d=b;d<=m;d++)  dp1[a][b][a][d] = min(row[a][d], d-b+1);
            for (int c=a;c<=n;c++)  dp1[a][b][c][b] = min(col[c][b], c-a+1);
            for (int c=a+1;c<=n;c++){
                for (int d=b+1;d<=m;d++)  if (s[c][d]=='0'){
                    dp1[a][b][c][d] = dp1[max(a,c-col[c][d]+1)][max(b,d-row[c][d]+1)][c-1][d-1] + min(col[c][d], c-a+1) + min(row[c][d], d-b+1) - 1;
                }
            }
        }
    }
    for (int a=1;a<=n;a++){
        for (int b=1;b<=m;b++){
            for (int c=a;c<=n;c++){
                for (int d=b;d<=m;d++){
                    dp2[a][b][c][d] = dp2[a][b][c][d-1] + dp2[a][b][c-1][d] - dp2[a][b][c-1][d-1] + dp1[a][b][c][d];
                }
            }
        }
    }
    return;
}