本文共 1648 字，大约阅读时间需要 5 分钟。

原题链接：

一：原题内容

3 41011100100013 4101010010001

42Note: Huge Input, scanf() is recommended.

二：分析理解

 枚举所有的尾行，然后对于每个尾行，记录到这行为止每列连续的1的个数，为了形象起见，我们可以把每列看做宽度为1，连续个数看做它的高度。然后问题就可以看做在一些高度可能为0的相邻矩形中找到最大矩形，即最大长方形那道题，如下图。

此题的另外一个条件是可以将列任意移动，我们肯定要尽量将高度大的放在一起，所以，我们可以将高度从小到大排序，然后有h[i-1]<=h[i]，

预处理出每个点下方有多个连续的1即cnt[i][j]，对每行的cnt值从大到小排序，枚举列dp即可，dp[i]表示以第i行为上边的矩形的面积最大值，转移方程：dp[i] = max(dp[i], j * cnt[i][j])

三：AC代码

#include
   
      #include
    
     #include
     
        using namespace std;int a[1005];int dp[1005];int main(){	int n, m;	char ch;	while (~scanf("%d%d", &n, &m))	{		int ans = -1;		for (int i = 1; i <= n; i++)		{			getchar();			for (int j = 1; j <= m; j++)			{				scanf("%c", &ch);				if (ch == '1')					a[j]++;				else					a[j] = 0;				dp[j] = a[j];			}			sort(dp + 1, dp + m + 1);			for (int k = 1; k <= m; k++)			{				if (dp[k] * (m - k + 1) > ans)					ans = dp[k] * (m - k + 1);			}		}		printf("%d\n", ans);	}	return 0;}
     
    
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/50963732 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！