poj3494 Largest Submatrix of All 1's 스택 + dp

2087 단어 단조 창고단조 대열
제목: m*n의 0/1 직사각형에서 가장 큰 전 1 직사각형을 찾아 그 면적을 구한다.
사고방식: 포j2794와 유사하다. 단지 이 문제는 2차원이지만 본질은 같다.dp[i][j]를 설정하여 (i, j)에서 가장 긴 연속의 1의 길이를 기록한다.사전 처리 완료
pp, 우리는 문제를 순서대로 i행위를 구하는 것으로 바꿀 수 있다. 제j열의 높이는 dp[i][j]이고 가장 큰 직사각형 면적을 구하는 것은 완전히 m차poj2794의 방법일 뿐이다.상세히 보다
코드:
// file name: poj3494.cpp //
// author: kereo //
// create time:  2014 11 05      20 32 35  //
//***********************************//
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int MAXN=2000+100;
const double eps=1e-8;
const int inf=0x3fffffff;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
int m,n;
int l[MAXN],r[MAXN],dp[MAXN][MAXN];
struct node{
	int h,index;
}p[MAXN];
stacks;
int main()
{
	while(~scanf("%d%d",&m,&n)){
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				int x;
				scanf("%d",&x);
				if(x == 0)
					dp[i][j]=0;
				else 
					dp[i][j]=dp[i-1][j]+1;
			}
		}
		int ans=0;
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				p[j].index=j; p[j].h=dp[i][j];
				if(s.empty()){
					l[j]=r[j]=j;
					s.push(p[j]);
				}
				else{
					node temp=s.top();
					if(temp.h
=p[j].h){
							node temp=s.top(); s.pop();
							index=temp.index;
							if(temp.h == p[j].h)
								r[index]=p[j].index;
							else 
								r[index]=p[j].index-1;
						}
						s.push(p[j]);
						l[j]=l[index]; r[j]=j;
					}
				}
			}
			int index=s.top().index;
			while(!s.empty()){
				node temp=s.top(); s.pop();
				int id=temp.index;
				r[id]=index;
			}
			for(int j=1;j<=n;j++)
				ans=max(ans,(r[j]-l[j]+1)*p[j].h);
		}
		printf("%d
",ans);
	}
	return 0;
}
드릴 작업 시작 설명서
칸수 or쪽지 보내기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage