6549번: 히스토그램에서 가장 큰 직사각형
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤
www.acmicpc.net
boj 2104 부분배열 고르기
www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉,..
emoney96.tistory.com
이 문제와 같은 풀이방법입니다.
세그먼트 트리로 구간의 최솟값만 트리에 저장하였습니다.
구간 [l, r]의 최솟값의 인덱스를 query함수로 찾아내고 list[idx]에 구간의 길이를 곱한 값이 직사각형의 넓이입니다.
idx를 기준으로 왼쪽(l, idx - 1) 구간, 오른쪽(idx + 1, r) 구간의 넓이와 [l, r]에서 구했던 넓이의 최댓값을 출력하면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int tree[] = new int[400004];
static long list[] = new long[100001];
static int N;
static int init(int node, int s, int e) {
if (s == e)
return tree[node] = s;
int m = (s + e) / 2;
int l = init(node * 2, s, m);
int r = init(node * 2 + 1, m + 1, e);
return tree[node] = list[l] < list[r] ? l : r;
}
static int query(int node, int s, int e, int l, int r) {
if (l > e || s > r)
return -1;
if (l <= s && e <= r)
return tree[node];
int m = (s + e) / 2;
int a = query(node * 2, s, m, l, r);
int b = query(node * 2 + 1, m + 1, e, l, r);
if (a == -1)
return b;
else if (b == -1)
return a;
else
return list[a] < list[b] ? a : b;
}
static long func(int l, int r) {
int idx = query(1, 1, N, l, r);
long sum = list[idx] * (r - l + 1);
if (idx > l)
sum = Math.max(sum, func(l, idx - 1));
if (idx < r)
sum = Math.max(sum, func(idx + 1, r));
return sum;
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
if (N == 0)
return;
for (int i = 1; i <= N; i++) {
list[i] = Integer.parseInt(st.nextToken());
}
init(1, 1, N);
}
public static void main(String[] args) throws Exception {
while (true) {
input();
if (N == 0)
break;
sb.append(func(1, N)).append("\n");
}
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > SegmentTree' 카테고리의 다른 글
| boj 14438 수열과 쿼리 17 (0) | 2021.02.21 |
|---|---|
| boj 13537 수열과 쿼리 1 (0) | 2021.02.21 |
| boj 2104 부분배열 고르기 (0) | 2021.02.19 |
| boj 2243 사탕상자 (0) | 2021.02.04 |
| boj 2042 구간 합 구하기 (0) | 2021.01.23 |