hdu2830_经典dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2830

题意：给你一个由0 和 1组成的矩阵，任意两列可以调换，求最大全部为1的子矩阵，输出1的个数

与杭电2870类似

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <map>
 9 using namespace std;
10 
11 char num[1010][1010];
12 int dp[1010][1010];
13 int n, m, res;
14 map <int, int> mp;
15 
16 void find()
17 {
18     for (int i = 1; i <= n; i++)
19     {
20         mp.clear();
21         for (int j = 1; j <= m; j++)
22             mp[dp[i][j]]++;
23         map <int , int>::iterator it = mp.end();
24         int temp = 0;
25         for (; it != mp.begin(); it--){
26             temp += it->second;//大的高度可以截短啊，对不对
27             res = max(it->first * temp, res);//高度 * 所在高度的宽度
28         }
29     }
30 }
31 int main()
32 {
33     while (~scanf("%d %d", &n, &m))
34     {
35         res = 0;
36         for (int i = 1; i <= n; i++)
37             scanf("%s", num[i] + 1);
38         memset(dp, 0, sizeof(dp));
39         for (int j = 1; j <= m; j++)
40         {
41             for (int i = 1; i <= n; i++)
42             {
43                 if (num[i][j] == '1')
44                     dp[i][j] = dp[i - 1][j] + 1;
45             }
46         }
47         find();
48         printf("%d
", res);
49     }   
50     return 0;
51 }