CFR 372 B. Counting Rectangles is Fun ( DP, Inclusion Exclusion )

Problem - B - Codeforces

題意：
給一個 0 / 1 矩陣，Q 筆詢問，求以 ( A, B ) 為左上角，( C, D ) 為右下角的矩陣中，有多少不同的矩形元素全為 0。

資料規模：
There are three integers in the first line: n, m and q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3e5). Each of the next n lines contains m characters — the grid. Consider grid rows are numbered from top to bottom, and grid columns are numbered from left to right. Both columns and rows are numbered starting from 1.
Each of the next q lines contains a query — four integers that describe the current rectangle, a, b, c, d (1 ≤ a ≤ c ≤ n; 1 ≤ b ≤ d ≤ m).
TL: 4000 ms
ML: 256 MB

解法：
顯然可以來個四次方。考慮四次狀態：
dp[ i ][ j ][ k ][ l ]：以 ( i, j ) 為右下角，( k, l ) 為左上角時，這個矩陣是否元素全為 0
pdp[ i ][ j ][ k ][ l ]：以 i 為右下角的右界，j 為右下角的下界，( k, l ) 為左上角時，有多少矩陣元素全為 0
這個轉移需要想清楚一點，因為左上角總是固定的，所以先不管，而右下界是向右下延伸，所以要從左上開始。
ans[ i ][ j ][ k ][ l ]：題目所求

時間 / 空間複雜度：
O( N^2 * M^2 )

注意：
這種多維動態規劃，順序很重要，想清楚在某個狀態時需要知道哪些狀態。

int N, M, Q;
vs G;

void init(){
  cin >> N >> M >> Q;
  G = vs( N );
  for( int i = 0; i < N; ++i ){
    cin >> G[ i ];
  }
}

int dp[ 40 + 1 ][ 40 + 1 ][ 40 + 1 ][ 40 + 1 ]; // [ x ][ y ][ up_x ][ left_y ]
int pdp[ 40 + 1 ][ 40 + 1 ][ 40 + 1 ][ 40 + 1 ];
int ans[ 40 + 2 ][ 40 + 2 ][ 40 + 2 ][ 40 + 2 ];

void preprocess(){
  for( int i = 0; i <= 40; ++i ){
    for( int j = 0; j <= 40; ++j ){
      for( int k = 0; k <= 40; ++k ){
        for( int l = 0; l <= 40; ++l ){
          if( k <= i and l <= j ) continue;
          dp[ i ][ j ][ k ][ l ] = 1;
        }
      }
    }
  }
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j < M; ++j ){
      for( int k = i; k >= 0; --k ){
        for( int l = j; l >= 0; --l ){
          dp[ i + 1 ][ j + 1 ][ k + 1 ][ l + 1 ] = dp[ i ][ j + 1 ][ k + 1 ][ l + 1 ] & dp[ i + 1 ][ j ][ k + 1 ][ l + 1 ] & ( G[ i ][ j ] == '0' );
        }
      }
    }
  }
  for( int i = 1; i <= N; ++i ){
    for( int j = 1; j <= M; ++j ){
      for( int k = i; k >= 1; --k ){
        for( int l = j; l >= 1; --l ){
          pdp[ i ][ j ][ k ][ l ] = pdp[ i - 1 ][ j ][ k ][ l ] + pdp[ i ][ j - 1 ][ k ][ l ] - pdp[ i - 1 ][ j - 1 ][ k ][ l ] + dp[ i ][ j ][ k ][ l ];
        }
      }
    }
  }
  for( int i = N; i >= 1; --i ){
    for( int j = M; j >= 1; --j ){
      for( int k = i; k >= 1; --k ){
        for( int l = j; l >= 1; --l ){
          ans[ i ][ j ][ k ][ l ] = ans[ i ][ j ][ k + 1 ][ l ] + ans[ i ][ j ][ k ][ l + 1 ] - ans[ i ][ j ][ k + 1 ][ l + 1 ] + pdp[ i ][ j ][ k ][ l ];
        }
      }
    }
  }
}

void solve(){
  for( int kase = 0; kase < Q; ++kase ){
    int A, B, C, D; cin >> A >> B >> C >> D;
    cout << ans[ C ][ D ][ A ][ B ] << endl;
  }
}