首页 > 代码库 > 51nod 1158 全是1的最大子矩阵

51nod 1158 全是1的最大子矩阵

题目链接:51nod 1158 全是1的最大子矩阵

题目分类是单调栈,但是直接用与解最大子矩阵类似的办法水过了。。

 

技术分享
 1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #define CLR(a,b) memset((a),(b),sizeof((a))) 6 using namespace std; 7 const int N = 501; 8 const int inf = 0x3f3f3f3f; 9 int n, m;10 int dp[N][N];11 int main(){12     int i, j, k, ans, x, h;13     scanf("%d%d", &m, &n);14     CLR(dp, 0);15     for(i = 1; i <= n; ++i){16         for(j = 1; j <= m; ++j){17             scanf("%d", &x);18             if(x) dp[i][j] = x + dp[i-1][j];19         }20     }21     ans = 0;22     for(i = 1; i <= m; ++i){23         for(j = 1 ; j <= n; ++j){24             h = inf;25             for(k = i; k <= m; ++k){26                 h = min(h, dp[j][k]);27                 if(h == 0) break;28                 ans = max(ans, (k-i+1) * h);29             }30         }31     }32     printf("%d\n", ans);33     return 0;34 }
View Code

 

51nod 1158 全是1的最大子矩阵