글 읽기 - 이렇게 풀면 안되나요?

p_ce1052 3년 전 0

x좌표 기준으로 2분할하여 왼쪽 오른쪽 걸쳐있는 경우의 직사각형들의 최대 넓이를 구하였습니다. 걸쳐 있는 경우에서 시간 초과가 나는 것 같은데 제 생각에 시간복잡도는 x길이를 절반으로 쪼개기 때문에 logM, 각각의 경우에서 중간에 걸쳐있는 직사각형을 구하는데 (nm+n^2)이 걸리므로 t * O((nm + n^2)logm) 입니다. 아예 로그를 없애야 하는 문제인가요? 분할정복으로 된다면 어떻게 더 최적화해야될지 모르겠습니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
int n,m;
bool arr[1005][1005];
int dp[1005][1005];
int get_min(int x,int start,int fin){
	int ret = INT32_MAX;
	for(int i=start; i<=fin; i++) ret = min(ret,dp[i][x]);
	return ret;
}
void proccess_left(int x_start,int x_fin){
	for(int i=0; i<n; i++){
		dp[i][x_fin] = 0;
		for(int j=x_fin; j>=x_start; j--){
			if(arr[i][j]) dp[i][x_fin]++;
			else break;
		}
	}
}
void proccess_right(int x_start,int x_fin){
	for(int i=0; i<n; i++){
		dp[i][x_start] = 0;
		for(int j=x_start; j<=x_fin; j++){
			if(arr[i][j]) dp[i][x_start]++;
			else break;
		}
	}
}
int f(int l,int r){
	int ret = 0;
	if(l==r){
		for(int i=0; i<n; i++) dp[i][l] = 0;
		for(int i=0; i<n; i++){
			if(arr[i][l]) dp[i][l] = 1;
			else continue;
			if(i) dp[i][l]+=dp[i-1][l];
			ret = max(ret,dp[i][l]);
		}
		return ret;
	}
	else{
		int mid = (l+r)/2;
		ret = max(f(l,mid),f(mid+1,r));
		proccess_left(l,mid);
		proccess_right(mid+1,r);
		for(int i=0; i<n; i++){
			int left_min = dp[i][mid];
			int right_min = dp[i][mid+1];
			for(int j=i; j<n; j++){
				left_min = min(left_min,dp[j][mid]);
				right_min = min(right_min,dp[j][mid+1]);
				ret = max(ret,(left_min+right_min)*(j-i+1));
			}
		}
		return ret;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	while(1){
		cin>>n>>m;
		if(n+m==0) return 0;
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++) scanf("%d",arr[i]+j);
		}
		cout<<f(0,m-1)<<'\n';
	}
}

p_ce1052 3년 전 0

급한대로 히스토그램 풀이를 가져와서 새로 짠 t * O( mn * logm )은 통과가 되네요 아직도 위 풀이는 왜 통과가 안되는지 모르겠습니다 ... 테스트케이스 개수를 알려주시면 좋겠네요 그에 맞춰서 계산할 수 있게

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이렇게 풀면 안되나요?

p_ce1052 3년 전 0

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말