1/*
2 * ๊ณ ๊ธ DP ์ต์ ํ (Advanced DP Optimization)
3 * CHT, D&C Optimization, Knuth Optimization, Monotonic Queue
4 *
5 * DP์ ์๊ฐ ๋ณต์ก๋๋ฅผ ์ค์ด๋ ๊ณ ๊ธ ๊ธฐ๋ฒ๋ค์
๋๋ค.
6 */
7
8#include <iostream>
9#include <vector>
10#include <deque>
11#include <algorithm>
12#include <climits>
13#include <cmath>
14
15using namespace std;
16
17typedef long long ll;
18const ll INF = LLONG_MAX / 2;
19
20// =============================================================================
21// 1. Convex Hull Trick (CHT)
22// =============================================================================
23
24class ConvexHullTrick {
25private:
26 struct Line {
27 ll m, b; // y = mx + b
28 ll eval(ll x) const { return m * x + b; }
29 };
30
31 deque<Line> hull;
32
33 bool bad(const Line& l1, const Line& l2, const Line& l3) {
34 // l2๊ฐ ๋ถํ์ํ์ง ํ์ธ
35 return (l3.b - l1.b) * (l1.m - l2.m) <= (l2.b - l1.b) * (l1.m - l3.m);
36 }
37
38public:
39 // ๊ธฐ์ธ๊ธฐ ๋จ์กฐ ๊ฐ์์ผ ๋ ์ถ๊ฐ
40 void addLine(ll m, ll b) {
41 Line line = {m, b};
42 while (hull.size() >= 2 && bad(hull[hull.size()-2], hull[hull.size()-1], line)) {
43 hull.pop_back();
44 }
45 hull.push_back(line);
46 }
47
48 // x๊ฐ ๋จ์กฐ ์ฆ๊ฐํ ๋ ์ต์๊ฐ ์ฟผ๋ฆฌ
49 ll query(ll x) {
50 while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x)) {
51 hull.pop_front();
52 }
53 return hull[0].eval(x);
54 }
55
56 // ์ด๋ถ ํ์์ผ๋ก ์ฟผ๋ฆฌ (x๊ฐ ๋จ์กฐ ์ฆ๊ฐ๊ฐ ์๋ ๋)
57 ll queryBinarySearch(ll x) {
58 int lo = 0, hi = hull.size() - 1;
59 while (lo < hi) {
60 int mid = (lo + hi) / 2;
61 if (hull[mid].eval(x) > hull[mid + 1].eval(x)) {
62 lo = mid + 1;
63 } else {
64 hi = mid;
65 }
66 }
67 return hull[lo].eval(x);
68 }
69};
70
71// =============================================================================
72// 2. Li Chao Tree
73// =============================================================================
74
75class LiChaoTree {
76private:
77 struct Line {
78 ll m, b;
79 ll eval(ll x) const { return m * x + b; }
80 };
81
82 struct Node {
83 Line line;
84 Node *left, *right;
85 Node() : line({0, INF}), left(nullptr), right(nullptr) {}
86 };
87
88 Node* root;
89 ll lo, hi;
90
91 void update(Node*& node, ll l, ll r, Line newLine) {
92 if (!node) node = new Node();
93
94 ll mid = (l + r) / 2;
95 bool leftBetter = newLine.eval(l) < node->line.eval(l);
96 bool midBetter = newLine.eval(mid) < node->line.eval(mid);
97
98 if (midBetter) swap(node->line, newLine);
99
100 if (l == r) return;
101
102 if (leftBetter != midBetter) {
103 update(node->left, l, mid, newLine);
104 } else {
105 update(node->right, mid + 1, r, newLine);
106 }
107 }
108
109 ll query(Node* node, ll l, ll r, ll x) {
110 if (!node) return INF;
111
112 ll mid = (l + r) / 2;
113 ll result = node->line.eval(x);
114
115 if (x <= mid) {
116 result = min(result, query(node->left, l, mid, x));
117 } else {
118 result = min(result, query(node->right, mid + 1, r, x));
119 }
120
121 return result;
122 }
123
124public:
125 LiChaoTree(ll lo, ll hi) : root(nullptr), lo(lo), hi(hi) {}
126
127 void addLine(ll m, ll b) {
128 update(root, lo, hi, {m, b});
129 }
130
131 ll query(ll x) {
132 return query(root, lo, hi, x);
133 }
134};
135
136// =============================================================================
137// 3. D&C Optimization
138// =============================================================================
139
140// dp[i][j] = min(dp[i-1][k] + cost[k][j]) for k < j
141// ์กฐ๊ฑด: opt[i][j] <= opt[i][j+1]
142
143class DivideConquerDP {
144private:
145 int n, k;
146 vector<vector<ll>> dp;
147 vector<vector<ll>> cost;
148
149 void compute(int level, int lo, int hi, int optLo, int optHi) {
150 if (lo > hi) return;
151
152 int mid = (lo + hi) / 2;
153 int opt = optLo;
154 dp[level][mid] = INF;
155
156 for (int i = optLo; i <= min(mid - 1, optHi); i++) {
157 ll val = dp[level - 1][i] + cost[i + 1][mid];
158 if (val < dp[level][mid]) {
159 dp[level][mid] = val;
160 opt = i;
161 }
162 }
163
164 compute(level, lo, mid - 1, optLo, opt);
165 compute(level, mid + 1, hi, opt, optHi);
166 }
167
168public:
169 ll solve(int n, int k, const vector<vector<ll>>& cost) {
170 this->n = n;
171 this->k = k;
172 this->cost = cost;
173
174 dp.assign(k + 1, vector<ll>(n + 1, INF));
175 dp[0][0] = 0;
176
177 // ์ฒซ ๋ฒ์งธ ๊ทธ๋ฃน
178 for (int j = 1; j <= n; j++) {
179 dp[1][j] = cost[1][j];
180 }
181
182 for (int i = 2; i <= k; i++) {
183 compute(i, 1, n, 0, n - 1);
184 }
185
186 return dp[k][n];
187 }
188};
189
190// =============================================================================
191// 4. Knuth Optimization
192// =============================================================================
193
194// dp[i][j] = min(dp[i][k] + dp[k+1][j]) + cost[i][j] for i <= k < j
195// ์กฐ๊ฑด: opt[i][j-1] <= opt[i][j] <= opt[i+1][j]
196
197ll knuthOptimization(int n, const vector<vector<ll>>& cost) {
198 vector<vector<ll>> dp(n + 2, vector<ll>(n + 2, 0));
199 vector<vector<int>> opt(n + 2, vector<int>(n + 2));
200
201 // ๊ธฐ์ ์กฐ๊ฑด
202 for (int i = 1; i <= n; i++) {
203 opt[i][i] = i;
204 }
205
206 // ๊ธธ์ด ์์ผ๋ก ๊ณ์ฐ
207 for (int len = 2; len <= n; len++) {
208 for (int i = 1; i + len - 1 <= n; i++) {
209 int j = i + len - 1;
210 dp[i][j] = INF;
211
212 int lo = opt[i][j - 1];
213 int hi = opt[i + 1][j];
214 if (lo < i) lo = i;
215 if (hi > j - 1) hi = j - 1;
216
217 for (int k = lo; k <= hi; k++) {
218 ll val = dp[i][k] + dp[k + 1][j] + cost[i][j];
219 if (val < dp[i][j]) {
220 dp[i][j] = val;
221 opt[i][j] = k;
222 }
223 }
224 }
225 }
226
227 return dp[1][n];
228}
229
230// =============================================================================
231// 5. Monotonic Queue Optimization
232// =============================================================================
233
234// dp[i] = min(dp[j]) + cost[i] for j in [i-k, i-1]
235
236vector<ll> monotonicQueueDP(int n, int k, const vector<ll>& cost) {
237 vector<ll> dp(n + 1);
238 deque<int> dq;
239
240 dp[0] = 0;
241 dq.push_back(0);
242
243 for (int i = 1; i <= n; i++) {
244 // ์๋์ฐ ๋ฒ์ด๋ ์์ ์ ๊ฑฐ
245 while (!dq.empty() && dq.front() < i - k) {
246 dq.pop_front();
247 }
248
249 // ์ต์๊ฐ ์ฌ์ฉ
250 dp[i] = dp[dq.front()] + cost[i];
251
252 // ์ ์์ ์ถ๊ฐ (๋ชจ๋
ธํ ๋ ์ ์ง)
253 while (!dq.empty() && dp[dq.back()] >= dp[i]) {
254 dq.pop_back();
255 }
256 dq.push_back(i);
257 }
258
259 return dp;
260}
261
262// =============================================================================
263// 6. SOS DP (Sum over Subsets)
264// =============================================================================
265
266void sosDP(vector<ll>& dp, int n) {
267 // dp[mask]์ mask์ ๋ชจ๋ ๋ถ๋ถ์งํฉ์ ํฉ ์ ์ฅ
268 for (int i = 0; i < n; i++) {
269 for (int mask = 0; mask < (1 << n); mask++) {
270 if (mask & (1 << i)) {
271 dp[mask] += dp[mask ^ (1 << i)];
272 }
273 }
274 }
275}
276
277// =============================================================================
278// 7. Aliens Trick (WQS Binary Search)
279// =============================================================================
280
281// ์ ํํ k๊ฐ ์ ํ ๋ฌธ์ ๋ฅผ ํ๋ํฐ ฮป๋ก ๋ณํ
282// dp[i] = max(value[i] - ฮป)์ ํํ๋ก ๋ณํ ํ ์ด๋ถ ํ์
283
284pair<ll, int> alienDP(int n, const vector<ll>& values, ll penalty) {
285 // ํ๋ํฐ ฮป๋ฅผ ์ ์ฉํ์ ๋์ ์ต๋๊ฐ๊ณผ ์ ํ ๊ฐ์ ๋ฐํ
286 ll maxVal = 0;
287 int count = 0;
288
289 for (int i = 0; i < n; i++) {
290 ll val = values[i] - penalty;
291 if (val > 0) {
292 maxVal += val;
293 count++;
294 }
295 }
296
297 return {maxVal, count};
298}
299
300ll aliensOptimization(int n, int k, const vector<ll>& values) {
301 ll lo = 0, hi = 1e18;
302 ll result = 0;
303
304 while (lo <= hi) {
305 ll mid = (lo + hi) / 2;
306 auto [val, cnt] = alienDP(n, values, mid);
307
308 if (cnt >= k) {
309 result = val + k * mid;
310 lo = mid + 1;
311 } else {
312 hi = mid - 1;
313 }
314 }
315
316 return result;
317}
318
319// =============================================================================
320// ํ
์คํธ
321// =============================================================================
322
323int main() {
324 cout << "============================================================" << endl;
325 cout << "๊ณ ๊ธ DP ์ต์ ํ ์์ " << endl;
326 cout << "============================================================" << endl;
327
328 // 1. Convex Hull Trick
329 cout << "\n[1] Convex Hull Trick" << endl;
330 ConvexHullTrick cht;
331 cht.addLine(-2, 4); // y = -2x + 4
332 cht.addLine(-1, 3); // y = -x + 3
333 cht.addLine(0, 2); // y = 2
334
335 cout << " ์ง์ : y=-2x+4, y=-x+3, y=2" << endl;
336 cout << " x=0 ์ต์๊ฐ: " << cht.queryBinarySearch(0) << endl;
337 cout << " x=1 ์ต์๊ฐ: " << cht.queryBinarySearch(1) << endl;
338 cout << " x=2 ์ต์๊ฐ: " << cht.queryBinarySearch(2) << endl;
339
340 // 2. Li Chao Tree
341 cout << "\n[2] Li Chao Tree" << endl;
342 LiChaoTree lct(0, 100);
343 lct.addLine(-2, 10);
344 lct.addLine(1, 0);
345 lct.addLine(-1, 8);
346
347 cout << " ์ง์ : y=-2x+10, y=x, y=-x+8" << endl;
348 cout << " x=0 ์ต์๊ฐ: " << lct.query(0) << endl;
349 cout << " x=3 ์ต์๊ฐ: " << lct.query(3) << endl;
350 cout << " x=5 ์ต์๊ฐ: " << lct.query(5) << endl;
351
352 // 3. ๋ชจ๋
ธํ ๋ ํ DP
353 cout << "\n[3] ๋ชจ๋
ธํ ๋ ํ DP" << endl;
354 vector<ll> cost = {0, 1, 3, 2, 4, 1, 5};
355 auto dp = monotonicQueueDP(6, 3, cost);
356 cout << " ๋น์ฉ: [1, 3, 2, 4, 1, 5], k=3" << endl;
357 cout << " DP: [";
358 for (int i = 1; i <= 6; i++) {
359 cout << dp[i];
360 if (i < 6) cout << ", ";
361 }
362 cout << "]" << endl;
363
364 // 4. SOS DP
365 cout << "\n[4] SOS DP" << endl;
366 vector<ll> sos = {1, 2, 3, 4, 5, 6, 7, 8}; // 2^3 = 8
367 cout << " ์ด๊ธฐ: [1, 2, 3, 4, 5, 6, 7, 8]" << endl;
368 sosDP(sos, 3);
369 cout << " SOS: [";
370 for (int i = 0; i < 8; i++) {
371 cout << sos[i];
372 if (i < 7) cout << ", ";
373 }
374 cout << "]" << endl;
375
376 // 5. ๋ณต์ก๋ ๋น๊ต
377 cout << "\n[5] ๋ณต์ก๋ ๋น๊ต" << endl;
378 cout << " | ๊ธฐ๋ฒ | ์๋ ๋ณต์ก๋ | ์ต์ ํ ํ |" << endl;
379 cout << " |-------------------|-------------|--------------|" << endl;
380 cout << " | CHT | O(nยฒ) | O(n log n) |" << endl;
381 cout << " | Li Chao Tree | O(nยฒ) | O(n log C) |" << endl;
382 cout << " | D&C ์ต์ ํ | O(knยฒ) | O(kn log n) |" << endl;
383 cout << " | Knuth ์ต์ ํ | O(nยณ) | O(nยฒ) |" << endl;
384 cout << " | ๋ชจ๋
ธํ ๋ ํ | O(nk) | O(n) |" << endl;
385 cout << " | SOS DP | O(3^n) | O(n ร 2^n) |" << endl;
386 cout << " | Aliens Trick | O(nยฒ) | O(n log C) |" << endl;
387
388 // 6. ์ ์ฉ ์กฐ๊ฑด
389 cout << "\n[6] ์ ์ฉ ์กฐ๊ฑด" << endl;
390 cout << " CHT:" << endl;
391 cout << " - dp[i] = min(dp[j] + a[j] ร b[i]) ํํ" << endl;
392 cout << " - a[j] ๋๋ b[i]๊ฐ ๋จ์กฐ" << endl;
393 cout << " D&C ์ต์ ํ:" << endl;
394 cout << " - opt[i][j] <= opt[i][j+1]" << endl;
395 cout << " - Quadrangle Inequality" << endl;
396 cout << " Knuth ์ต์ ํ:" << endl;
397 cout << " - opt[i][j-1] <= opt[i][j] <= opt[i+1][j]" << endl;
398 cout << " - ๊ตฌ๊ฐ DP์์ ์ฃผ๋ก ์ฌ์ฉ" << endl;
399
400 cout << "\n============================================================" << endl;
401
402 return 0;
403}