首页 > 代码库 > 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 }
51nod 1158 全是1的最大子矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。