题意:M x N 的01矩阵(1 ≤ N,M ≤ 1000),任意两列可以交换,求由1组成的最大子矩阵的面积。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2830
——>>枚举每行作为子矩阵的底,用个缓存数组拿下1的高度,排序。。
时间复杂度:O(N * M * log(M))
#include <cstdio> #include <cstring> #include <algorithm> using std::sort; using std::max; const int MAXN = 1000 + 10; int N, M; int h[MAXN], buf[MAXN]; int ret; int main() { char ch; while (scanf("%d%d", &N, &M) == 2) { ret = 0; memset(h, 0, sizeof(h)); for (int i = 1; i <= N; ++i) { getchar(); for (int j = 1; j <= M; ++j) { ch = getchar(); if (ch == '1') { ++h[j]; } else { h[j] = 0; } } memcpy(buf, h, sizeof(h)); sort(buf + 1, buf + 1 + M); for (int j = 1; j <= M; ++j) { ret = max(ret, (M - j + 1) * buf[j]); } } printf("%d\n", ret); } return 0; }