题意：给你一个40×40的01矩形，现在给你q个询问（1,1000000），一个矩形中有多少矩形和为0。
解题思路：DP，n^4预处理，主要是两个状态转移方程
1)dp[i][j][s] = dp[i][j-1][s] + 1 (mp[i][j] == 0 )
2)ans[lx][ly][i][j] += ans[lx][ly][i-1][j] + ans[lx][ly][i][j-1] - ans[lx][ly][i-1][j-1]
解题代码：
1 // File Name: 372b.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月29日 星期日 20时52分13秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define maxn 45 26 using namespace std; 27 int n , m, q; 28 int dp[maxn][maxn][maxn]; 29 int val[maxn][maxn]; 30 int ans[maxn][maxn][maxn][maxn]; 31 int mp[maxn][maxn]; 32 void solve(int lx,int ly) 33 { 34 memset(dp,0,sizeof(dp)); 35 for(int i = lx ;i <= n;i ++) 36 for(int j = ly ;j <= m;j ++) 37 { 38 for(int s = i ;s >= lx ; s --) 39 { 40 if(mp[s][j] == 0 ) 41 { 42 dp[i][j][s] = dp[i][j-1][s] + 1; 43 ans[lx][ly][i][j] += dp[i][j][s]; 44 }else{ 45 break; 46 } 47 } 48 ans[lx][ly][i][j] += ans[lx][ly][i-1][j] + ans[lx][ly][i][j-1] - ans[lx][ly][i-1][j-1] ; 49 } 50 } 51 int main(){ 52 scanf("%d %d %d",&n,&m,&q); 53 for(int i = 1;i <= n;i ++) 54 { 55 for(int j = 1;j <= m;j ++) 56 { 57 scanf("%1d",&mp[i][j]); 58 } 59 } 60 for(int i =1 ;i <= n;i ++) 61 for(int j = 1;j <= m;j ++) 62 { 63 solve(i,j); 64 } 65 int lx,ly,rx,ry; 66 while(q--) 67 { 68 scanf("%d %d %d %d",&lx,&ly,&rx,&ry) ; 69 printf("%d ",ans[lx][ly][rx][ry]); 70 } 71 return 0; 72 }