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]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 것이
www.acmicpc.net
6549번: 히스토그램에서 가장 큰 직사각형
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤
www.acmicpc.net
이문제와 같은 방법으로 해결하였습니다.
우선 세그먼트 트리로 구간 합과 최솟값을 모두 tree배열에 저장하였습니다.
그 다음 func함수에서 [s, e]구간의 최솟값의 인덱스(idx)과 구간 합(query)을 찾아내어 곱한 값을 sum에 저장하고,
idx를 기준으로 왼쪽(s, idx - 1), 오른쪽(idx + 1, e) 구간으로 나누어 각각의 sum의 최댓값을 찾은 후에 출력하였습니다.
이 방법말고 다른방법으로 해결하는 방법이 있던데 알려주신 분의 코드를 뜯어봐야 할 것 같습니다...
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
|
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 long tree[][] = new long[400004][2];
static int list[] = new int[100001];
static int N;
static long[] init(int node, int s, int e) {
if (s == e) {
tree[node][0] = list[s];
tree[node][1] = s;
return tree[node];
}
int m = (s + e) / 2;
long l[] = init(node * 2, s, m);
long r[] = init(node * 2 + 1, m + 1, e);
tree[node][0] = l[0] + r[0];
if (list[(int) l[1]] < list[(int) r[1]])
tree[node][1] = l[1];
else
tree[node][1] = r[1];
return tree[node];
}
static long query(int node, int s, int e, int l, int r) {
if (s > r || l > e)
return 0;
if (l <= s && e <= r)
return tree[node][0];
int m = (s + e) / 2;
return query(node * 2, s, m, l, r) + query(node * 2 + 1, m + 1, e, l, r);
}
static long findmin(int node, int s, int e, int l, int r) {
if (s > r || l > e)
return -1;
if (l <= s && e <= r)
return tree[node][1];
int m = (s + e) / 2;
long a = findmin(node * 2, s, m, l, r);
long b = findmin(node * 2 + 1, m + 1, e, l, r);
if (a == -1)
return b;
else if (b == -1)
return a;
else {
if (list[(int) a] > list[(int) b])
return b;
else
return a;
}
}
static long func(int s, int e) {
int idx = (int) findmin(1, 1, N, s, e);
long sum = query(1, 1, N, s, e) * list[idx];
if (s < idx)
sum = Math.max(sum, func(s, idx - 1));
if (idx < e)
sum = Math.max(sum, func(idx + 1, e));
return sum;
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
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 {
input();
System.out.println(func(1, N));
}
}
|
cs |
'algorithm > SegmentTree' 카테고리의 다른 글
| boj 14438 수열과 쿼리 17 (0) | 2021.02.21 |
|---|---|
| boj 13537 수열과 쿼리 1 (0) | 2021.02.21 |
| boj 6549 히스토그램에서 가장 큰 직사각형 (0) | 2021.02.19 |
| boj 2243 사탕상자 (0) | 2021.02.04 |
| boj 2042 구간 합 구하기 (0) | 2021.01.23 |