it外包一个人可以赚多少_网站建设合同百度文库_企业网站排名优化公司_汉川seo推广

题目描述

现在有一个 $n\times m$ 的 $01$ 矩阵，矩阵的行与行可以互相交换，我们现在想知道在一个最优的交换方案中，其中最大的全 $1$ 子矩阵能有多大。

输入格式

第一行两个整数 $n,m$。
接下来 $n$ 行，每行一个长度为 $m$ 的 $01$ 字符串，描述这个 $01$ 矩阵。

输出格式

一个数，即最大的全 $1$ 子矩阵面积。

样例

样例输入1：

2 2
10
11

样例输出1：

2

样例输入2：

4 3
100
011
000
101

样例输出2：

2

数据范围

对于 $30\%$ 的数据，$n,m\le 10$。
对于 $70\%$ 的数据，$n,m\le 1000$。
对于 $100\%$ 的数据，$n,m\le 5000$。

题解

对于 $30\%$ 的数据，直接枚举左上，右上，左下，右下四个端点，判断内部是否全 $1$ 即可。
如果用前缀和优化，可以得到 $40$ 分。

考虑固定左端点，枚举右端点，看有多少行满足条件，计算即可。
先预处理每行每个位置向后延申的最大 $1$ 序列的结尾，用双指针求。
接下来枚举左右端点，看每行从左端点开始是否大于右端点。
复杂度为 $\Theta (n\times m)$，但是还是 $70$ 分，常数大了。

输入 n, m 和数组 a
//预处理每个位置向后延申的最大1序列的结尾 
for(int i = 1; i <= n; ++ i){//第 i 行int l = 0, r = 1;while(l <= r && r <= m){++ l;r = max(r, l);if(a[i][l] == 0){f[i][l] = -1;continue;}while(a[i][r] == 1){++ r;}-- r;f[i][l] = r;} 
}
//l 为左端点
int l = 0, ans = 0;
while(l < m){++ l;//找到能扩展的最大右端点int s = 0;for(int i = 1; i <= n; ++ i){s = max(s, f[i][l]);} //记录 prv 进行优化，l 到 r 和 l 到 r + 1 是单调不增的，如果当前长度乘上上一个的数量小于答案，返回int prv = n;for(int j = l; j <= s; ++ j){if((j - l + 1) * prv <= ans){continue;}//统计有多少行满足条件int sum = 0;for(int i = 1; i <= n; ++ i){if(f[i][l] >= j){++ sum;}}prv = sum;ans = max(ans, sum * (j - l + 1));}
}
printf("%d\n", ans);

进行常数优化。

1. 舍弃预处理数组，在输入时直接统计当前行连续长度的个数。
2. 输入时不要用 $\%1d$，直接输入字符数组，会快很多。

for(int i = 1; i <= n; ++ i){scanf("%s", a);//连续长度统计int s = 0;for(int j = 1; j <= m; ++ j){if(a[j - 1] == '1'){++ s;fl[j][s] ++;}else{s = 0;}}
}
int l = 0, ans = 0;
while(l < m){++ l;int s = 0;//从 m 开始，比 i 长度长的就不用重新统计了for(int i = m; i >= 0; -- i){s += fl[l][i];if(s * i > ans){ans = s * i;}}
}
printf("%d\n", ans);