bzoj 1057 （悬线法求最大子矩阵）

bzoj 1057

悬线法求最大子矩阵

#include <bits/stdc++.h> using namespace std; const int N = 2010; int s[N][N], l[N][N], r[N][N], up[N][N]; int n, m, ans1, ans2; int main(){ #ifdef ONLINE_JUDGE #elsefreopen("in.txt", "r", stdin); #endif //ONLINE_JUDGEwhile(~scanf("%d%d", &n, &m)){ans1 = ans2 = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &s[i][j]);l[i][j] = r[i][j] = j;up[i][j] = 1;}}for(int i = 1; i <= n; i++){for(int j = 2; j <= m; j++){if(s[i][j] == 1 - s[i][j - 1]){l[i][j] = l[i][j - 1];}}}for(int i = 1; i <= n; i++){for(int j = m - 1; j >= 1; j--){if(s[i][j] == 1 - s[i][j + 1]){r[i][j] = r[i][j + 1];}}}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(i > 1 && s[i][j] == 1 - s[i - 1][j]){up[i][j] = up[i - 1][j] + 1;l[i][j] = max(l[i][j], l[i - 1][j]);r[i][j] = min(r[i][j], r[i - 1][j]);}int t = r[i][j] - l[i][j] + 1;int tt = min(t, up[i][j]);ans1 = max(ans1, tt*tt);ans2 = max(ans2, t * up[i][j]);}}printf("%d\n%d\n", ans1, ans2);}return 0; }