题意：给你一个矩型，问你其中长度为k且内部都是1的矩型有多少个。
解题思路：dp，先求出一个行与列 的连续个数，然后再进行dp ，dp[i][j][s] += dp[i-1][j-1][s-1]; 不过这里要用到滚动数组
解题代码：
1 // File Name: range.c 2 // Author: darkdream 3 // Created Time: 2014年04月07日 星期一 17时23分06秒 4 /* 5 ID: dream.y1 6 PROG: range 7 LANG: C++ 8 */ 9 #include<stdio.h> 10 #include<string.h> 11 #include<stdlib.h> 12 #include<time.h> 13 #include<math.h> 14 #include<limits.h> 15 16 int map[300][300]; 17 int hang[300][300]; 18 int lie[300][300]; 19 int dp[4][251][251]; 20 int main(){ 21 22 freopen("range.in","r",stdin); 23 freopen("range.out","w",stdout); 24 25 26 int n ; 27 scanf("%d",&n); 28 memset(hang,0,sizeof(hang)); 29 memset(lie,0,sizeof(lie)); 30 memset(dp,0,sizeof(dp)); 31 for(int i =1 ;i <= n;i ++) 32 for(int j = 1;j <= n;j ++) 33 scanf("%1d",&map[i][j]); 34 for(int i = 1;i <= n;i ++) 35 { 36 for(int j = 1;j <= n;j ++) 37 { 38 if(map[i][j]) 39 hang[i][j] = hang[i][j-1] + 1; 40 } 41 } 42 for(int i = 1;i <= n;i ++) 43 { 44 for(int j = 1;j <= n;j ++) 45 { 46 if(map[j][i]) 47 lie[j][i] = lie[j-1][i] + 1; 48 } 49 } 50 /* for(int i = 1;i<= n;i ++) 51 { 52 for(int j = 1;j <= n;j ++) 53 printf("%d ",hang[i][j]); 54 printf(" "); 55 } 56 printf(" "); 57 for(int i = 1;i<= n;i ++) 58 { 59 for(int j = 1;j <= n;j ++) 60 printf("%d ",lie[i][j]); 61 printf(" "); 62 } 63 printf(" ");*/ 64 int ans[300]; 65 memset(ans,0,sizeof(ans)); 66 for(int i = 2; i <= n;i ++) 67 { 68 for(int j = 2;j <= n; j ++) 69 { 70 int k = hang[i][j] > lie[i][j]?lie[i][j]:hang[i][j]; 71 if(map[i-1][j-1]) 72 dp[1][j-1][1] = 1; 73 74 for(int s = 2;s <= k ; s ++ ) 75 dp[2][j][s] += dp[1][j-1][s-1]; 76 77 } 78 for(int j = 2;j <= n;j ++) 79 for(int s = 2;s <= n;s ++) 80 { 81 ans[s] += dp[2][j][s]; 82 } 83 84 memcpy(dp[1],dp[2],sizeof(dp[2])); 85 memcpy(dp[2],dp[3],sizeof(dp[3])); 86 } 87 88 for(int i =2;i <= n;i ++) 89 if(ans[i]) 90 printf("%d %d ",i,ans[i]); 91 return 0 ; 92 }