boj 12846 무서운 아르바이트
https://www.acmicpc.net/problem/12846
12846번: 무서운 아르바이트
성화는 악독하기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다. 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다. 돈은 당일에 주지 않고 퇴직을 할 때 한
www.acmicpc.net
일을 연속적으로 해야하며, 한 번만 할 수 있습니다.
또한 일을 한 기간동안 가장 작은 일급 * 기간의 돈을 받습니다.
가장 작은 일급이 10이고, 5일동안 일해서 받은 50보다
가장 작은 일급이 20이고, 3일동안 일해서 받은 60이 더 많은 이익을 챙길 수 있습니다.
이 문제는 히스토그램 문제와 요구하는 것이 같으며,
https://emoney96.tistory.com/139
boj 6549 히스토그램에서 가장 큰 직사각형
www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주
emoney96.tistory.com
https://emoney96.tistory.com/138
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
두 문제와 동일한 풀이입니다.
트리에는 가장 작은 일급을 가진 인덱스를 저장합니다.
init 함수로 전 구간의 최소 인덱스를 저장합니다.
그리고 partition 함수를 통해 해당 구간에서 가장 작은 값을 가지는 인덱스를 query 함수로 찾은 후 최대 이익을 갱신합니다.
해당 인덱스는 가장 작은 값이므로 제외하고, [s ~ idx - 1] [idx + 1 ~ e] 구간으로 나누어서 같은 과정을 반복합니다.
|
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
|
#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
typedef long long ll;
ll tree[MAX * 4], list[MAX], ans;
int N;
void init(int node, int s, int e) {
if (s == e) {
tree[node] = s;
return;
}
int m = (s + e) / 2;
init(node * 2, s, m);
init(node * 2 + 1, m + 1, e);
int l = tree[node * 2];
int r = tree[node * 2 + 1];
if (list[l] < list[r]) tree[node] = l;
else tree[node] = r;
return;
}
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 lIdx = query(node * 2, s, m, l, r);
int rIdx = query(node * 2 + 1, m + 1, e, l, r);
if (lIdx == -1) {
return rIdx;
}
else if (rIdx == -1) {
return lIdx;
}
else {
return list[lIdx] < list[rIdx] ? lIdx : rIdx;
}
}
void partition(int s, int e) {
if (s > e) return;
int idx = query(1, 1, N, s, e);
ans = max(ans, list[idx] * (ll)(e - s + 1));
partition(s, idx - 1);
partition(idx + 1, e);
}
void func() {
init(1, 1, N);
partition(1, N);
cout << ans << '\n';
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> list[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |