2019牛客暑期多校训练营（第二场）H——Second Large Rectangle（思维题，求第二大全1矩阵）

链接：https://ac.nowcoder.com/acm/contest/882/H
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Given a N×MN×M binary matrix. Please output the size of second large rectangle containing all "1""1".

Containing all "1""1" means that the entries of the rectangle are all "1""1".
 

A rectangle can be defined as four integers x1,y1,x2,y2x1,y1,x2,y2 where 1≤x1≤x2≤N1≤x1≤x2≤N and 1≤y1≤y2≤M1≤y1≤y2≤M. Then, the rectangle is composed of all the cell (x, y) where x1≤x≤x2x1≤x≤x2 and y1≤y≤y2y1≤y≤y2. If all of the cell in the rectangle is "1""1", this is a valid rectangle.

Please find out the size of the second largest rectangle, two rectangles are different if exists a cell belonged to one of them but not belonged to the other.

输入描述:

The first line of input contains two space-separated integers N and M.
Following N lines each contains M characters cijcij.

1≤N,M≤10001≤N,M≤1000
N×M≥2N×M≥2
cij∈"01"cij∈"01"

输出描述:

Output one line containing an integer representing the answer. If there are less than 2 rectangles containning all "1""1", output "0""0".

示例1

输入

复制

1 2
01

输出

复制

0

示例2

输入

复制

1 3
101

输出

复制

1

题意：求第二大全1矩阵

题解：用dp[i][j]表示这个位置，往上延伸最多有多少个连续的1，结构体存的是矩形的高 和 宽的左边坐标，然后暴力一行一行找~~

感觉会超时，结果没超时，还贼快~~

上代码：（此代码max1是第一大，max2是第二大，所以第一大，第二大都能求~~哈哈~~）

#include <iostream>
using namespace std;
const int MAX = 1e3+400;
int max1,max2,top;//max1是第一大的值，max2是第二大的值
struct hh{
	int l,h;
	hh(int _l=0,int _h=0):l(_l),h(_h){}
}q[MAX];
int dp[MAX][MAX],s[MAX][MAX];
void update(int x){
	if(x>=max1){
		max2=max1;
		max1=x;
	}
	else if(x>max2){
		max2=x;
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n;i++){
		for (int j = 1; j <= m;j++){
			scanf("%1d",&dp[i][j]);
			s[i][j]=dp[i][j];
			dp[i][j]+=dp[i][j]*dp[i-1][j];//保存向上延伸最多有多少个1
		}
	}
	for (int i = 1; i <= n;i++){
		top=0;
		for (int j = 1; j <= m;j++){
			if(s[i][j]==0) top=0;//有一个是0，就要重新开始找，前面无法再包括进去，只能往后找
			else{
				int tmp=j;
				while(q[top].h>dp[i][j]&&top) tmp=q[top--].l;//找到宽符合是全1矩阵的位置
				if(q[top].h!=dp[i][j]) q[++top]=hh(tmp,dp[i][j]);
				for (int k = 1; k <= top;k++){
					update(q[k].h*(j-q[k].l+1));//更新最大、第二大的值
				}
			}
		}
	}
	printf("%d\n",max2);//输出第二大的值
	return 0;
}