2024. 2. 14. 03:40ㆍPS/백준
본 글은 다음 세 논문을 바탕으로 쓰여 있습니다.
우리는 크기가 $p\times q$, $q\times r$인 두 행렬을 곱하는 cost를 $pqr$이라고 생각합니다. 행렬 $M_{1}\times \cdots \times M_{n-1}$을 곱하는데 필요한 최소의 연산 횟수는 얼마일까요? $M_{i}$의 크기를 $w_{i}\times w_{i+1}$이라고 두고 $w_{1}$부터 시계 방향으로 꼭짓점에 $w_{i}$들을 할당하여 $w_{n}$으로 끝나는 아래의 볼록 다각형을 생각해봅시다.
Part 1. Lemma 1에서는 위 볼록 다각형을 partition하는 것이 행렬들의 연산 순서와 대응된다고 합니다. 볼록 다각형의 partition의 cost는 partition으로 만들어지는 삼각형들의 각 가중치를 합하여 얻는데 $\triangle w_{p}w_{q}w_{r}$의 가중치는 $w_{p}w_{q}w_{r}$로 구합니다. 그럼 우리는 볼록 다각형의 최적의 partition을 찾아 그 cost를 구하면 됩니다.
가중치가 낮은 순서대로 $w_{i}$들을 정렬했을 때 앞에서부터 해당하는 vertex를 $V_{i}$로 부릅니다. 즉, 가중치가 가장 낮은 vertex는 $V_{1}$, 가장 큰 vertex는 $V_{n}$입니다. partial order $<$를 정의하는데 $V_{i}<V_{j}$ if $w_{i}<w_{j}$ or $w_{i}=w_{j},\ i < j$ 입니다.
우리는 여러 최적의 partition 중에서도 사전적으로 가장 낮은 l-optimum partition에 관심이 있습니다. 먼저 h-arc를 정의합시다. 볼록 다각형에서 변을 이루고 있는 것을 side라고 하며 한 vertex와 인접하지 않은 vertex를 이은 선을 arc라고 합니다. 어느 partition에서든지 하나의 arc는 유일한 내접 사각형을 이등분합니다. $V_{x}-V_{z}$가 사각형$V_{x},V_{w},V_{z},V_{y}$(시계 방향으로 적은 vertex)를 이등분한다고 합시다. 이때 이 arc가 h-arc가 될 필요충분조건은 아래와 같습니다.
\[\min(w_{x},w_{z}) >\min(w_{y},w_{w}),\ \ \ \ \max(w_{x},w_{z})<\max(w_{y},w_{w})\]
이제 우리가 $V_{x}-V_{z}$를 임의로 잡았다고 해봅시다. $V_{w}$를 $V_{x}$에서 시계 방향으로 $V_{z}$까지 돌았을 때 나오는 가장 낮은 order를 가지는 vertex라고 합시다. $V_{y}$를 $V_{z}$에서 시계 방향으로 $V_{x}$까지 돌았을 때 나오는 가장 낮은 order를 가지는 vertex라고 합시다. 이때 $V_{x}-V_{z}$가 h-arc가 될 필요조건은 $V_{y}<V_{x}<V_{z}<V_{w}$입니다. (part 1. corollary 4) 따라서 우리는 이 조건을 만족하는 arc를 potential h-arc라고 부릅니다. 이 potential h-arc들은 partiton에 관계 없이 존재하지 않거나 존재하다면 서로 겹치지 않습니다.(이를 논문에서는 compatible이라 부릅니다. part 1.Theorem 4) 이 성질을 이용하면 l-optimum partition에 존재하는 h-arc들을 포함하는 potential h-arc들의 집합을 얻는 알고리즘을 찾을 수 있습니다. 그것이 바로 one-sweep 알고리즘입니다.
Part 2에서는 l-optimum partition을 구하는 알고리즘이 설명되어 있습니다.
먼저 fan을 정의합니다. fan은 말 그대로 선풍기 모양을 하는 partition을 의미합니다. 예를 들어 $\{w_{1},w_{2},\cdots,w_{n}\}$이 꼭짓점이고 $w_{1}$의 가중치가 가장 작은 볼록 다각형을 생각하면 이 볼록 다각형의 fan은 아래와 같습니다. 그리고 이것을 $Fan(w_{1}|w_{2},\cdots,w_{n})$이라고 표현합니다. 또한 Fan의 cost는 $w_{1}(w_{2}w_{3}+w_{3}w_{4}+w_{4}w_{5}+\cdots+w_{n-1}w_{n})$과 같고 옆으로 계속 이어지며 곱하는 것을 $(w_{2}:w_{n})$이라고 정의하면 $w_{1}(w_{2}:w_{n})$이 됩니다.
part 2. lemma 1는 potential h-arc가 존재하지 않는 l-optimum partition은 fan이라고 말합니다. 이는 볼록 다각형의 부분 집합으로 이루어진 subpolygon에서도 성립하기 때문에 우리는 potential h-arc가 존재하는지 안하는지를 따져서 l-optimum partition을 얻을 수 있습니다.(만약 어떤 subpolygon에서 potential h-arc가 존재하지 않으면 subpolygon의 l-optimum partition은 fan입니다!) part 2. lemma 2에서는 potential h-arc들 간에는 항상 포함 관계(일명 "above")가 있다고 말합니다. potential h-arc들은 특성상 $V_{n}$에 가까울수록 above에 있습니다. 또한 $V_{1}$에 가까울수록 below에 있습니다. $V_{1},V_{n}$들을 degenerated h-arc(일반적이지 않은 h-arc를 말합니다. 각 vertex는 실제로 arc가 아닙니다.)로 생각한다면 potential h-arc들 간의 order를 줄 수 있고 이것은 tree의 형태로 나타날 것입니다. 이것을 arc tree라고 합니다.
우리가 어떤 potential h-arc를 최적의 partition에 등장시킬 수 있다면 그로 인해 나타나는 cost는 반드시 fan보다 작아야 합니다. 위의 polygon에서 $w_{2}-w_{n}$을 potential h-arc라고 가정해봅시다. 그리고 subpolygon $\{w_{2},w_{3},\cdots,w_{n}\}$이 fan 구조를 이룬다고 합시다. 그럼 이 partition의 cost는 $Fan(w_{2}|w_{3},\cdots,w_{n})+w_{1}w_{n}w_{2}$이고 이 값이 $w_{1}(w_{2}:w_{n})$보다 작아야 합니다. 따라서 다음이 성립해야 합니다.
\[\frac{w_{2}(w_{3}:w_{n})}{(w_{2}:w_{n})-w_{2}w_{n}}<w_{1}\]
일반적으로, potential h-arc $V_{i}-V_{k}$의 등장을 위해서는 다음이 성립해야 합니다. 이때 $ C(w_{i},\cdots,w_{k})$는 subpolygon $\{w_{i},\cdots,w_{k}\}$의 최적의 cost 입니다.
\[\frac{C(w_{i},\cdots,w_{k})}{(w_{i}:w_{k})-w_{i}w_{k}}<w_{1}\]
그럼 이 사실을 subpolygon에 대해서도 적용해봅시다.
potential h-arc $V_{i}-V_{k}$와 $V_{p},V_{r},V_{n},V_{s},V_{q}$로 둘러싸인 subpolygon에서 $V_{p}-V_{q}$가 fan보다 더 저렴한 cost를 가지기 위해서는 다음을 만족해야 합니다.
\[\frac{C(w_{p},w_{r},w_{n},w_{s},w_{q})}{(w_{p}:w_{q})-w_{p}w_{q}}<\min(w_{i},w_{k}) \ \ (*)\]
만약 위 부등식이 만족되었다면 $V_{p}-V_{q}$는 위 subpolygon에 대해 positive라고 말합니다.
이제 임의의 potential h-arc $V_{j}-V_{j}'$($h_{j}$) 에 대해서 supporting weight를 정의합니다. $h_{j}$보다 위에 있는 potential h-arc를 $V_{k}-V_{k}'$($h_{k}$)라고 합시다. 이때 $h_{k}$에 대한 $h_{j}$의 supporting weight는
\[S(h_{j}\backslash h_{k})=\frac{C(w_{j},w_{k},w_{k}',w_{j}')}{(w_{j}:w_{j}')-((w_{k}:w_{k}')-w_{k}w_{k'})-w_{j}w_{j}'}\]
입니다. 만약 $h_{i},h_{j},h_{k}$가 세 potential h-arc이고 $h_{i}<h_{j}<h_{k}$를 만족한다면 다음을 알 수 있습니다.
\[S(h_{i}\backslash h_{j})=\frac{a}{b}\ \ \ S(h_{j}\backslash h_{k})=\frac{c}{d}\ \ \implies\ \ S(h_{i}\backslash h_{k})=\frac{a+c}{b+d}\]
이 표기를 이용해서 (*)을 다시 쓰면 아래와 같습니다.
\[S(h_{p}\backslash h_{n})<\min(w_{i},w_{k})\]
일반적인 polygon에서는 potential h-arc가 선형적이지 않은 tree 구조를 형성하기 때문에 $h_{j}$의 위에 있는 potential h-arc들을 여러개 상정해야 하나의 subpolygon이 결정되게 됩니다. 따라서 $S(h_{j}\backslash X)$를 정의하고 $X$는 $h_{j}$위의 potential h-arc들의 집합입니다.
지금부터 arc는 potential h-arc를 대신합니다.
새로운 개념인 ceiling을 정의합니다. 아래 조건을 만족하면 $h_{k}$는 $h_{i}$의 ceiling이 됩니다.
(i) $h_{n}$의 ceiling은 $h_{n}$입니다.
(ii) $h_{k}>h_{i}$과 $S(h_{i}\backslash h_{k})>S(h_{k}\backslash h_{k} \text{'s ceiling})$를 만족시키는 가장 낮은 arc입니다.
father-son relation을 정의합니다. 다음 조건을 만족시키는 $h_{j}$는 $h_{i}$의 son입니다.($h_{i}$는 $h_{j}$의 father입니다.)
(i) $h_{j}>h_{i}$, $S(h_{j}\backslash h_{j} \text{'s ceiling} )<\min(w_{i},w_{i}')$ ($w_{i},w_{i}'$들은 $h_{i}$의 양 끝 가중치입니다.)
(ii) $S(h_{i}\backslash h_{j}) \le S(h_{j}\backslash h_{j} \text{'s ceiling} )$ i.e. $h_{j}$는 $h_{i}$의 ceiling이 아닙니다.
(iii) 조건 (i),(ii)를 만족시키는 가장 높은 arc입니다.
논문의 관찰에 의하면 어떤 arc $h_{i}$가 있을 때 son들은 $h_{i}$와 $h_{i} \text{'s ceiling} $ 사이에 있습니다. 또한 son들의 ceiling은 $h_{i} \text{'s ceiling} $보다 낮습니다. 즉, 어떤 arc와 그 ceiling 사이의 공간을 하나의 block이라고 보면 일종의 nested block structure가 있는 셈입니다.
part 2. Thm 6에 의하면 $h_{j}$의 l-optimum partition에서의 존재성의 $h_{j}$의 son들의 존재성과 동치입니다.
part 2. Thm 7에 의하면 $h_{i}<h_{j}$이고 $h_{i}$와 $h_{j}$ 사이의 l-optimum partition이 fan이라고 했을 때 $S(h_{j}\backslash h_{j} \text{'s ceiling} )\ge \min(w_{i},w_{i}')$이면 $h_{j}$와 그 son들은 l-optimum partition에 존재할 수 없습니다.
두 Thm을 이용하면 아래의 알고리즘을 얻을 수 있습니다.
1. One sweep 알고리즘으로 potential h-arc들을 얻어내자.
2. potential h-arc들로 arc tree를 만들고 arc tree의 leaf부터(가장 높은 곳) 검사를 시작하자.
3. $h_{j}$의 검사를 한다고 하자. $h_{j}$의 바로 위에 있는 arc들의 집합을 $X$라고 하자. 그 집합 안에 있는 arc 중에서 $h_{m}$을 뽑고 이것이 $S(h_{m}\backslash h_{m} \text{'s ceiling} )\ge \min(w_{i},w_{i}')$를 만족한다고 하자. $h_{m}$과 $h_{j}$ 사이에는 fan이 가장 저렴한 partition임이 보장되어 있다. 따라서 Thm7을 적용하면 $h_{m}$와 그 son들은 존재할 수 없다. $h_{m}$와 그 son들을 삭제한다. 이것을 $X$에 있는 모든 arc에 대해 실행한다.
4. 위의 결과인 X를 사용한다. 3번 과정을 진행하면서 $S(h_{j}\backslash X)$를 계산했다. 만약 $ S(h_{j}\backslash X)\le S(h_{m}\backslash h_{m} \text{'s ceiling} )$이면 $h_{m}$은 $h_{j}$의 son이다.(part 2. Thm 8) son의 존재는 $h_{j}$의 존재와 동치임으로 son을 $X$에서 제거한다.
5. X에 $S(h_{j}\backslash h_{j}\text{'s ceiling})$를 추가한다.
이것이 알고리즘의 대략적인 형태입니다. 그럼 보다 세부적인 구현 사항에 대해 알아보도록 합시다.
이 알고리즘이 참이라고 한다면 $h_{j}$의 검사가 끝났을 경우, $h_{j}$바로 아래에 $h_{i}$가 있다고 할 때, $X$에 들어있는 것은 $h_{j}$를 포함한 $h_{i}$의 바로 위에 있는 arc들 입니다. 여기서 "바로 위"라는 것은 전체 potential h-arc를 고려해서 바로 위에 있는 것이 아니라, 이미 지워질 것은 지워진 후의 상태에서 바로 위에 있는 것입니다. 따라서 5번 과정에서 $X$에 $h_{j}$의 supporting weight를 추가하였습니다.
3번 과정에서 $h_{m}$와 그 son들을 삭제한다고 하였는데, 이는 사실 $h_{m}$만 제거해도 충분합니다. $h_{m}$이 처리되는 과정에서 4번 단계를 거치면 $h_{m}$의 son들은 $h_{m}$으로 압축되기 때문입니다. 그럼 $X$는 $X-\{h_{m}\}\cup \{h_{m} \text{'s ceiling}\}$로 바뀌게 됩니다. 집합 $X$가 supporting weight에 쓰이는 순간은 4번 $S(h_{j}\backslash X)$에서 입니다. 기본적인 $S(h_{j}\backslash \{h_{n}\})$을 계산해 두었다고 합시다. 3번에서 $X$가 $X-\{h_{m}\}\cup \{h_{m}\text{'s ceiling}\}$로 변할 때 분모는 $h_{m}$이 차지하고 있었던 공간만큼 커집니다. 하지만 분자는 다시 계산해야 합니다. 그 이유는 이 순간 $S(h_{j}\backslash X)$의 구조가 fan이 되었기 때문입니다. 앞서 fan을 구하는 공식을 보았습니다. 이를 상기하면 $Fan(w_{1}|w_{2},\cdots,w_{n})=w_{1}(w_{2}:w_{n})$ 입니다. $h_{j}$의 작은쪽 가중치가 $w_{j}$라고 합시다. 그럼 $S(h_{j}\backslash \{h_{n}\})$의 분모는 $b=(w_{j}:w_{j'})-w_{j}w_{j'}$입니다. 놀랍게도 분자는 $b+w_{j}w_{j'}-w_{j}w_{j+1}$임을 알 수 있습니다. 만약 작은쪽 가중치가 $w_{j}'$이었다면 분자는 $b+w_{j}w_{j'}-w_{j'}w_{j'-1}$이 됩니다.
왼쪽의 경우를 먼저 보면, $w_{j}$의 한쪽이 $w_{j+1}$이 아닐지도 모릅니다. 우리는 복잡하게 생긴 구조의 fan을 구해야합니다. 마치 아래처럼 말입니다.
그럼 아까와 비슷하게 $b+w_{j}w_{j'}-w_{j}w_{p}$를 계산하면 됩니다. 잠깐, 어째서 $b$를 그대로 사용하는 것인가요? 사실 여기서 사용되는 $b$는 수정되어 온 값입니다. $h_{j}$를 검사하기 전에 반드시 검사해야 하는 arc들은 $h_{j}$의 하위 arc들(위에 있는 arc들) 입니다. 이 하위 arc들이 둘러싸고 있던 영역은 온전히 분모에 포함되어 있습니다. 따라서 $h_{j}$의 직속 하위 arc들의 분모 값을 $S(h_{j}\backslash \{h_{n}\})$의 분모에서 제외해야 $w_{j},w_{p},\cdots,w_{j'}$으로 이루어진 영역을 나타내는 분모를 얻습니다. 이렇게 얻어진 분모가 $b$로써 사용되는 것입니다. 그럼 $w_{p}$는 어떻게 구할 수 있을까요? $w_{j}$를 한쪽 꼭짓점으로 하는 arc가 언제 가장 최근 연결되었는지 살펴보면 됩니다. 가장 마지막으로 사용된 arc가 그 경계를 정할 것입니다. 이렇게 3번 과정에서 $S(h_{j}\backslash X)$를 계산했습니다.
4번 과정에서도 $S(h_{j}\backslash X)$는 변화합니다. 4번에서는 son들을 압축하는데 각 son을 삭제하는 순간 $h_{j}$ 자체는 홀로 차지해야 하는 영역이 증가합니다. 따라서 분모는 son의 분모만큼 더해집니다. 또한, son은 son이 차지했던 구역에서는 l-optimum partition을 이루었기에 $h_{j}$의 분모 즉, $h_{j}$가 차지하는 영역의 최적의 cost는 분모에 son의 분모를 더한 것이 될 것입니다. 4번 과정을 거친 이후에는 $S(h_{j}\backslash h_{j}\text{'s ceiling})$의 값이 남아있게 됩니다. $X$를 구성하는 과정에서 방문한 모든 arc들을 추가하기 때문에 son의 위에 son이 있더라도 4번 과정에서 처리할 수 있게 됩니다. 세부적으로 보면 결국 son들 사이사이는 다른 arc가 없습니다. 따라서 한 son의 ceiling은 다른 son의 ceiling이 되며 이것이 반복되어 결국 $h_{j}$의 ceiling에 도달합니다. (nested block structure) 이것이 $S(h_{j}\backslash h_{j}\text{'s ceiling})$의 값이 남게 되는 이유입니다.
이 알고리즘은 root부터 leaf로 dfs탐색을 하는 재귀함수로 생각할 수 있습니다. 첫번째 arc로 $V_{1}$을 호출하고 각 arc에서는 그 바로 위에 존재하는 arc들을 호출합니다(이들을 자식 arc라고 합시다.). 바로 자식 arc들에 대한 dfs가 종료되면 각 자식 arc의 $X$를 union하는 과정이 필요합니다. 3, 4번 과정 모두 $S(h_{m}\backslash h_{m}\text{'s ceiling})$가 큰 값 먼저 계산하는 것이 효율적이므로 $X$의 자료구조로 priority-queue를 선택하는 것이 좋습니다.
아래에는 이 과정을 구현한 코드기 있습니다. 이 코드는 아래의 링크를 참고하였습니다.
https://github.com/junodeveloper/Hu-Shing/blob/master/hu-shing.cpp
# 코드 보기
|
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
#include<bits/stdc++.h>
#define MAX 2000002
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
struct HArc{
int id; //determined in "new_arc"
int st, end;
int low; //lower weight's index
ll mul; //value of w[st] * w[end]
ll base;
ll num, den;
inline bool contains(HArc &b)const{
return st <= b.st && b.end <= end;
}
inline ll get_support()const{
return num / den;
}
bool operator<(const HArc& b)const{
return get_support()<b.get_support();
}
bool operator<=(const HArc& b)const{
return get_support()<=b.get_support();
}
bool operator==(const HArc& b)const{
return get_support()==b.get_support();
}
//operator need to defined in priority queue
} h[MAX];
ll w[MAX];
ll CP[MAX];
vector<P> arcs;
vector<int> tree[MAX];
vector<HArc> con[MAX];
priority_queue<HArc> pq[MAX];
int qid[MAX];
int sub[MAX]; //numbrer of childs
int n_arcs, n_pqs;
int n;
void new_arc(int st, int end){ //st <= end
++n_arcs;
h[n_arcs].id = n_arcs;
h[n_arcs].st = st;
h[n_arcs].end = end;
h[n_arcs].low = w[st] < w[end] ? st : end;
h[n_arcs].mul = w[st] * w[end];
h[n_arcs].base = CP[end] - CP[st] - h[n_arcs].mul;
}
void build_tree(){
vector<int> st;
new_arc(1, n + 1); // note that w[n+1]=w[1]
for(auto& arc: arcs){
new_arc(arc.first, arc.second);
while(!st.empty() && h[n_arcs].contains(h[st.back()])){
tree[n_arcs].push_back(st.back());
st.pop_back();
}
st.push_back(n_arcs);
}
while(!st.empty()){
tree[1].push_back(st.back());
st.pop_back();
}
}
void collect_h_arcs(){
int i;
vector<int> st;
vector<P> tmp;
for(i = 1;i <= n;i++){
while(st.size() >= 2 && w[st.back()] > w[i]){
tmp.push_back({st[st.size() - 2], i});
st.pop_back();
}
st.push_back(i);
}
for(auto& arc: tmp){
if(arc.first == 1 || arc.second == 1) continue;
arcs.push_back(arc);
}
}
void init(){
int i;
int V1 = min_element(w + 1, w + n + 1) - w;
rotate(w + 1, w + V1, w + n + 1);
w[n + 1] = w[1];
collect_h_arcs();
for(i = 2;i <= n + 1;i++){
CP[i] = CP[i - 1] + w[i - 1] * w[i];
}
build_tree();
}
ll get_mul(int node){
if(node == 1) return w[1] * w[2] + w[1] * w[n]; //w[n+1]=w[1] In fact, we have to discard w[n+1]'s weight
HArc &cur = h[node];
if(cur.st == cur.low){
if(con[cur.st].empty() || !cur.contains(con[cur.st].back())){
return w[cur.st] * w[cur.st + 1]; ///if it is just normal fan with side of original convex polygon .
}
return con[cur.st].back().mul; //if we have to calculate the fan with side "not of" original convex polyon but its side is one "arc".
}
else{
if(con[cur.end].empty() || !cur.contains(con[cur.end].back())){
return w[cur.end] * w[cur.end - 1]; //it is clockwise direction.
}
return con[cur.end].back().mul;
}
}
void add_arc(int node){
HArc &cur = h[node];
pq[qid[node]].push(cur);
con[cur.st].push_back(cur);
con[cur.end].push_back(cur);
}
void remove_arc(int node){
con[pq[qid[node]].top().st].pop_back();
con[pq[qid[node]].top().end].pop_back();
pq[qid[node]].pop();
}
void merge_pq(int node){
int idx_max = -1;
for(auto &arc: tree[node]){
if(idx_max == -1 || sub[idx_max] < sub[arc]) idx_max = arc;
}
qid[node] = qid[idx_max]; //to save the time, we pick the child having maximal number of childs.
auto &cur_pq = pq[qid[node]];
for(auto &arc: tree[node]){
if(arc == idx_max) continue;
auto &child_pq = pq[qid[arc]];
while(!child_pq.empty()){
cur_pq.push(child_pq.top());
child_pq.pop();
}
}
}
void dfs(int node){
HArc &cur = h[node];
sub[node] = 1;
if(tree[node].empty()){
qid[node] = ++n_pqs;
cur.den = cur.base;
cur.num = w[cur.low] * (cur.den + cur.mul - get_mul(node));
add_arc(node);
return;
}
cur.den = cur.base;
for(auto &arc: tree[node]){
dfs(arc);
sub[node] += sub[arc];
cur.den -= h[arc].base; //child node is right above current node. current node is surounded by childe node so, denom must be subtracted.
}
cur.num = w[cur.low] * (cur.den + cur.mul - get_mul(node));
merge_pq(node); //merging proirity queue of child's
auto &cur_pq = pq[qid[node]];
while(!cur_pq.empty() && cur_pq.top().get_support() >= w[cur.low]){ //removing negative arcs
auto hm = cur_pq.top();
cur.den += hm.den; //the space being filled so denom get larger
remove_arc(node);
cur.num = w[cur.low] * (cur.den + cur.mul - get_mul(node)); //but the space should be a "fan"
}
while(!cur_pq.empty() && cur <= cur_pq.top()){ //condensing son
auto hm = cur_pq.top();
cur.den += hm.den; //the space being filled so denom get larger
remove_arc(node);
cur.num += hm.num; //adding son's cost(this is not a fan but son's optimal partition)
}
add_arc(node);
}
ll solve(){
dfs(1);
ll ans = 0;
auto &cur = pq[qid[1]];
while(!cur.empty()){
ans += cur.top().num;
cur.pop();
}
return ans;
}
int main(){
int i;
scanf("%d", &n);
for(i = 1;i <= n;i++){
scanf("%lld %lld", &w[i], &w[i + 1]);
}
n++;
init();
printf("%lld", solve());
}
|
cs |
# 코드 닫기
'PS > 백준' 카테고리의 다른 글
| [BOJ 30913] 위수는 쿼리입니까? (2) | 2024.06.27 |
|---|---|
| [BOJ 20539] Xorshift64 (2) | 2024.01.31 |
| [BOJ 16709] Congruence Equation (0) | 2024.01.29 |
| [BOJ 28365] 점화식과 주기 (2) | 2024.01.25 |
| [BOJ 18918] 피보나치 수의 최대공약수의 합처럼 보이지만... × 25 (0) | 2024.01.22 |