2019 우 객 여름 다 교 훈련소 (2 차 전), H

1412 단어 데이터 구조
단조 로 운 스 택 은 최대 사각형 면적 을 구 할 수 있 으 며, 여 기 는 조금 만 변형 시 키 면 해결 할 수 있다.s [i] [j] 를 원 그림 으로 설정 하고 h [i] [j] 를 s [i] [j] 를 바탕 으로 하 는 사각형 의 최대 높이 입 니 다.모든 h [i] [j] 를 기록 한 다음 에 한 줄 씩 최대 사각형 면적 을 구하 면 됩 니 다.그러나 여기 서 마지막 으로 출력 해 야 할 것 은 두 번 째 사각형 의 면적 (겹 칠 수 있 습 니 다. 경 기 를 할 때 너무 복잡 하 게 생각 하여 겹 쳐 서 는 안 될 줄 알 았 습 니 다..) 이기 때문에 업데이트 할 때 약간의 변화 가 있어 야 합 니 다 (코드 참조).
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
char s[maxn][maxn];
int h[maxn][maxn]; 

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)	scanf("%s",s[i]);
	for(int j=0;j=1;--i)
		{
			if(s[i][j]=='0')	start=0;
			else start=1;
			if(start)		//     1
				h[i][j+1]=h[i+1][j+1]+1;
			else		//      1,    0
				h[i][j+1]=0;
		}
	}
	for(int i=1;i<=n;++i)	h[i][m+1]=h[i][0]=0;		//      ,         
	int ans=0,ma=0;	//ans     ,ma    
	for(int i=1;i<=n;++i)
	{
		stack S;	S.push(0);		//  0,  
		for(int j=1;j<=m+1;++j)	
		{
			while(h[i][j]

좋은 웹페이지 즐겨찾기