首页 > 代码库 > hdu 2830 Matrix Swapping II
hdu 2830 Matrix Swapping II
题目大意:
给出的矩阵每一列之间可以任意交换。
求出交换后得到的最大的子矩阵和。
思路分析:
height[i][j] 表示 位置 i j 往下有多少深度。
然后我们枚举每一行。
可以将所有的height 排序。
得到最大的矩阵和就一遍递推过去。
n*n*lgn。。。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define maxn 1005 using namespace std; int height[maxn][maxn]; char p[maxn][maxn]; int a[maxn]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%s",p[i]); for(int j=0;j<m;j++) { int now=0; for(int i=n-1;i>=0;i--) { if(p[i][j]=='1')now++; else now=0; height[i][j]=now; } } int ans=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) a[j]=height[i][j]; sort(a,a+m); int st=0; while(a[st]==0)st++; for(int j=st;j<m;j++) ans=max(ans,a[j]*(m-j)); } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。