글 읽기 - 반례를 찾지 못하겠습니다

orange4glace 8년 전 0

height[0] = -1

height[N+1] = 0 으로 두고

st 는 들어온 블럭의 index 값을 저장하고

st2는 해당 블럭의 넓이 계산이 시작되어야 하는 x값입니다.

블록을 하나씩 받았을 때

st의 top보다 현재 들어온 블럭이 높다면 스택에 바로 넣고

낮다면 이전 스택을 현재 블럭보다 낮은게 나올때 까지 빼면서 넓이를 계산해줍니다.

이 과정에서 현재 스택에 들어있는 블럭중 자기보다 높은 블럭을 계속 빼면서 넓이를 계산하게 되고

마지막으로 뺀 블럭이 현재 높이의 블럭의 계산이 시작될 x 지점이 됩니다.

여러가지 해봐도 음... 뭘까요ㅠㅠ

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iostream>
using namespace std;

#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y))

int Q, N, M;

long long heights[100005];
stack<int> st;
stack<int> st2;

int main() {

	scanf("%d", &N);
	while (N != 0) {

		long long ret = 0;
		for (int i = 1; i <= N; i++)
			scanf("%d", &heights[i]);
		heights[0] = -1;
		heights[N + 1] = 0;
		st.push(0);
		st2.push(0);
		for (int i = 1; i <= N + 1; i++) {
			long long now = heights[i];
			int stackLeft = i;
			while (true) {
				int hi = st.top();
				int hl = st2.top();
				if (heights[hi] <= now) break;
				long long di = (i - hl) * heights[hi];
				ret = MAX(di, ret);
				stackLeft = hl;
				st.pop();
				st2.pop();
			}
			if (heights[st.top()] != now) {
				st.push(i);
				st2.push(stackLeft);
			}
		}
		printf("%lld", ret);
		scanf("%d", &N);

	}
	return 0;
}

indioindio 8년 전 1

뉴라인을 붙여서 출력했더니 정답이 되네요.

orange4glace 8년 전 1

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

감사합니다!!!!

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

문제

문제

출처

ICPC

반례를 찾지 못하겠습니다

orange4glace 8년 전 0

indioindio 8년 전 1

orange4glace 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말