[Jobdu]題1497:面積最大の全1サブマトリクス

タイトルの説明:
1つのM*Nの行列の中で、すべての要素は0と1だけで、この行列の中から1つの面積の最大の全1サブ行列を探し出して、いわゆる最大は要素1の個数が最も多いことを指します. 
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力される最初の行は2つの整数m、n(1<=m、n<=1000):入力するマトリクスのサイズを表します.行列にはm行があり、各行にはn個の整数があり、それぞれ0または1であり、隣接する2つの数の間に厳密に1つのスペースで区切られている. 
出力:
各テストケースに対応して、出力マトリクスの中で面積が最も大きい全1サブマトリクスの要素数. 
サンプル入力:

2 2

0 0

0 0

4 4

0 0 0 0

0 1 1 0

0 1 1 0

0 0 0 0

サンプル出力:

0

4

上記の問題をヒストグラムの中で最大の矩形を求める面積に変換し、元の行列の各行を1つのヒストグラムと見なし、各行の各列の値がその行の上の1の個数である場合、ヒストグラムのアルゴリズムをそれぞれ利用して各行の中で最大値を解き、グローバル最大値を求める.コードは次のとおりです.
 

 1 #include <iostream>

 2 #include <stack>

 3 #include <cstdio>

 4 using namespace std;

 5  

 6 int m, n;

 7 int a[1000][1000];

 8 int b[2][1001];

 9 int f = 0;

10  

11 int getMax() {

12     stack<int> s;

13     b[f][n] = 0;

14     int max = 0, tmp;

15     for (int i = 0; i <= n; ++i) {

16         if (s.empty() || b[f][s.top()] < b[f][i]) {

17             s.push(i);

18         } else {

19             int idx = s.top();

20             s.pop();

21             tmp = b[f][idx] * (s.empty() ? i : i - s.top() - 1);

22             max = (max > tmp) ? max : tmp;

23             --i;

24         }

25     }

26     return max;

27 }

28  

29 void getRes() {

30     int max = getMax(), tmp;

31     ++f; f %= 2;

32     for (int i = 1; i < m; ++i) {

33         for (int j = 0; j < n; ++j) {

34             b[f][j] = (a[i][j] == 0) ? 0 : b[(f+1)%2][j] + 1;

35         }

36         tmp = getMax();

37         ++f; f %= 2;

38         max = (max > tmp) ? max : tmp;

39     }

40     cout << max << endl;

41 }

42  

43 int main() {

44     //freopen("1497.in", "r", stdin);

45     while (cin >> m >> n) {

46         f = 0;

47         for (int i = 0; i < m; ++i) {

48             for (int j = 0; j < n; ++j) {

49                 cin >> a[i][j];

50                 if (i == 0)

51                     b[0][j] = a[0][j];

52             }

53         }

54         getRes();

55     }

56     return 0;

57 }

58  

59 /**************************************************************

60     Problem: 1497

61     User: hupo250

62     Language: C++

63     Result: Accepted

64     Time:800 ms

65     Memory:5432 kb

66 ****************************************************************/