http://poj.org/problem?id=3494

http://zhuanlan.zhihu.com/qinchao/19873823

做法一：單調棧

http://poj.org/problem?id=2559

http://www.shuizilong.com/house/archives/ad-infinitum-math-programming-contest-september14

//}/* .................................................................................................................................. */ const int N = int(2e3) + 9; int A[N][N], h[N], l[N], r[N]; int n, m; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif while (~scanf("%d %d", &n, &m)){ REP_2_1(i, j, n, m) RD(A[i][j]); int z = 0; h[0] = 0, h[m+1] = 0; REP_1(i, n){ REP_1(j, m) h[j] = (A[i][j] == 1 ? h[j] + 1 : 0); stack<int> s; s.push(0); REP_1(i, m){ if (h[i]){ while (h[i] <= h[s.top()]) s.pop(); l[i] = s.top()+1; } else{ CLR(s); } s.push(i); } CLR(s); s.push(m+1); DWN_1(i, m, 1){ if (h[i]){ while (h[i] <= h[s.top()]) s.pop(); r[i] = s.top(); } else{ CLR(s); } s.push(i); } REP_1(i, m) checkMax(z, h[i]*(r[i]-l[i])); } OT(z); } }

做法二：懸線法

//}/* .................................................................................................................................. */ const int N = int(2e3) + 9; int A[N][N], h[N][N], l[N][N], r[N][N]; int n, m; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif fill(A[0], A[0]+N, 1); fill(r[0], r[0]+N, INF); while (~scanf("%d %d", &n, &m)){ REP_2_1(i, j, n, m) RD(A[i][j]); int z = 0; RST(h, l, r); REP_1(i, n){ FOR_1(j, 1, m) l[i][j] = A[i][j] ? l[i][j-1] + 1 : 0; DWN_1(j, m, 1) r[i][j] = A[i][j] ? r[i][j+1] + 1 : 0; REP_1(j, m) if (A[i][j] && A[i-1][j]){ h[i][j] = h[i-1][j] + 1; checkMin(l[i][j], l[i-1][j]); checkMin(r[i][j], r[i-1][j]); } REP_1(j, m) checkMax(z, (h[i][j]+1)*(r[i][j]+l[i][j]-1)); } OT(z); } }