Codeforces Round #221 (Div. 1) B. Maximum Submatrix 2 DP

链接：

http://codeforces.com/contest/375/problem/B

题意：

给出一个01矩阵，行与行之间可以互换位置，问能够得到最大的全1矩阵的面积。

题解：

定义dp[i][j]表示从i开始长度为j的有多少个

然后再求一下后缀，即dp[i][j]表示从i开始长度大于等于j的有多少个

最后遍历一下dp数组就可以了

开始的时候我是把每个起点的单独的放到vector里面，然后排序，结果tle在40个样例。。

代码：

31 int n, m;
32 VI v[MAXN];
33 int last[MAXN];
34 int dp[MAXN][MAXN];
35 
36 bool cmp(int a, int b) {
37     return a > b;
38 }
39 
40 int main() {
41     ios::sync_with_stdio(false), cin.tie(0);
42     cin >> n >> m;
43     rep(i, 0, n) {    
44         string s;
45         cin >> s;
46         memset(last, 0, sizeof(last));
47         per(i, 0, m) {
48             if (s[i] == '1') last[i] = last[i + 1] + 1;
49             else last[i] = 0;
50         }
51         rep(i, 0, m) if (last[i]) dp[i][last[i]]++;
52     }
53     int ans = 0;
54     rep(i, 0, m) per(j, 1, m) dp[i][j] += dp[i][j + 1];
55     rep(i, 0, m) rep(j, 1, m + 1) ans = max(ans, j*dp[i][j]);
56     cout << ans << endl;
57     return 0;
58 }