UVa 10502【dp】

题意:给定01矩阵，求有多少个由1构成的矩阵。1本事也算一个矩阵。

　　到最后还是想不出来。。。。。

　　每次枚举两行，从第i行到第j行，k枚举矩阵的宽(column)。这样就相当于每次看看每列i到j行之间是否全是1，是就累加tot，不是就tot置零。比如现在i=1，j=3，前k=3列为：

　　　　　i=1　　　1 1 1

　　　　　　　　　 1 1 1

　　　　　j=3　　　1 1 1

这时相当于竖着的长条都是1，所以k=1时，sum[1]=3,（因为当j=2、1时，sum的值已经计算过了，到这里由于值为1再加一下就是3了，也可以看成类似求竖着的largest empty interval）,tot++,ans+=tot;k=2时，sum[2]=3,tot++,ans+=tot...

这样算出来此时状态下ans=1+2+3=6.（把话说明白好难）

参考代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN = 107;
 6 int maps[MAXN][MAXN];
 7 int sum[MAXN];
 8 char s[MAXN];
 9 int row, col;
10 
11 int main()
12 {
13     while (scanf("%d", &row) == 1, row)
14     {
15         scanf("%d", &col);
16         memset(sum, 0, sizeof(sum));
17         for (int i = 1; i <= row; i++)
18         {
19             scanf("%s", s);
20             for (int j = 0; j<col; j++) {
21                 maps[i][j + 1] = s[j] - '0';
22             }
23         }
24         int ans = 0;
25         for (int i = 1; i <= row; i++)//从第i行开始
26         {
27             memset(sum, 0, sizeof(sum));//每次换i行时清空sum，因为第i行是基础，j行随它变动
28             for (int j = i; j <= row; j++)//到第j行
29             {
30                 int tot = 0;
31                 for (int k = 1; k <= col; k++)//依次枚举
32                 {
33                     sum[k] += maps[j][k];
34                     if (sum[k] != j - i + 1) tot = 0;//如果连续长度不满足tot清零
35                     else tot++;//否则累加
36                     ans += tot;//记录结果
37                 }
38             }
39         }
40         cout << ans << endl;
41     }
42     return 0;
43 }

当然，也可以行列互换，看成第i列到第j列的长条。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN = 107;
 6 int maps[MAXN][MAXN];
 7 int sum[MAXN];
 8 char s[MAXN];
 9 int row, col;
10 
11 int main()
12 {
13     while (scanf("%d", &row) == 1, row)
14     {
15         scanf("%d", &col);
16         memset(sum, 0, sizeof(sum));
17         for (int i = 1; i <= row; i++)
18         {
19             scanf("%s", s);
20             for (int j = 0; j<col; j++) {
21                 maps[i][j + 1] = s[j] - '0';
22             }
23         }
24         int ans = 0;
25         for (int i = 1; i <= col; i++)
26         {
27             memset(sum, 0, sizeof(sum));
28             for (int j = i; j <= col; j++)
29             {
30                 int tot = 0;
31                 for (int k = 1; k <= row; k++)
32                 {
33                     sum[k] += maps[k][j];
34                     if (sum[k] != j - i + 1) tot = 0;
35                     else tot++;
36                     ans += tot;
37                 }
38             }
39         }
40         cout << ans << endl;
41     }
42     return 0;
43 }

i、j看成列

而且有一个非常有意思的性质，当矩阵是n*n且全是1时，答案就是前n个数的立方和。