IOICamp Day1 下午 - 動態規劃 & 圖論

--- tags: IOICamp --- # IOICamp Day1 下午 - 動態規劃 & 圖論講師：waynetuinfor 講義 (動態規劃)：https://www.csie.ntu.edu.tw/~b07902024/dp-lecture.pdf 講義 (圖論)： [TOC] ## dp - 重複子問題 (overlapping subproblem) - 最優子結構 (optimal substructure) - 狀態 (state) - 轉移 (transition) - $O(N^x) \times O(N^y) = O(N^{x+y}) \rightarrow xD/yD$ - 適用最佳化問題、計數問題 **例1. LIS** ```cpp= int f(int i) { int res = i; for (int j = 1; j < i; ++j) { if (A[j] < A[i]) res = max(res, f(j) + 1); } } ``` $\mathcal{O}(N \times 2^N)$ ```cpp= int f(int i) { if (dp[i] > 0) return dp[i]; int res = i; for (int j = 1; j < i; ++j) { if (A[j] < A[i]) res = max(res, f(j) + 1); } return dp[i] = res; } ``` $\mathcal{O}(N^2)$ ### 實用技巧 - 增加轉移的維度 **例2. Pokemon Go** $dp(i,j) = \max(dp(i-1,j), dp(i-1,j-1) + exp(i-1,j-1) \times A_i) \rightarrow 錯誤$ $dp(i,j,k) = \max(dp(i-1,j,k), dp(i-1,j-1,k-B_i) + (k-B_i) \times A_i) \rightarrow 正確$ - 減少冗餘的狀態 **例3. Two Path** $dp(x_1,y_1,x_2,y_2) = value(x_1,y_1,x_2,y_2) + \max_{x_1',y_1',x_2',y_2'}dp(x_1',y_1',x_2',y_2') \rightarrow \mathcal{O}(N^4)$ > 離原點距離相同，以距離跟 $x~or~y$ 可以推算出另一維的位置 $\rightarrow \mathcal{O}(N^3)$。 $dp(x_1,x_2,k) = value() + \max_{x_1',x_2'}dp(x_1',x_2',k-1)$ - 以資料結構維護狀態 - 滾動陣列 **例4.** 在 $dp(i, *)$ 只跟 $dp(i-1, *)$ 有關係的時候，可以利用 $i$ 跟 $i-1$ 奇偶性不同來滾動 - 滾動陣列輸出解路徑被滾動掉了 $\rightarrow$ 改成只需求出每個點。分治！複雜度多帶一個 $\log$ - 狀態壓縮 **例5. DAG上最短路** 每個點有 $7$ 種顏色 `dp[kN][2][2][2][2][2][2][2]` 顯然爛爆 `dp[kN][1 << 7]` 方便很多 - 快速莫比烏斯變換 $\text{FMT (SOS dp)}$ (?) 參考資料：https://codeforces.com/blog/entry/45223 **例6. Sum Of Subset** $\displaystyle\hat f(S) = \sum_{S' \subseteq S}f(S')$ ```cpp= for (int s = 0; s < (1 << N); ++s) { dp[s] = f[0]; int subset = s; while (subset > 0) { dp[s] += f[subset]; subset = (subset - 1) & s; } } ``` $\mathcal{O}(3^N)$ $L(S,i) = S$ 的子集中跟 $S$ 前 $i$ 個一樣的人 $dp(S,i) = \begin{array}{lcr} dp(S,i+1) & \mbox{if} ~ i \notin S\\ dp(S,i+1)+dp(S \backslash \{i\},i+1) & \mbox{if} ~ i\in S \end{array}$ ### 單調隊列優化 (?) **例7. Sliding Windows** ```cpp= deque<int> dq; for (int i = K, j = i; i <= N; ++i) { while (j <= i) { while (!dq.empty() and A[j] < A[dq.back()]) dp.pop_back(); dq.push_back(j++); } while (!dq.empty() and i - dq[0] >= K) dp.pop_front(); ans[i] = A[dq[0]]; } ``` 均攤分析：$\mathcal{O}(N)$ **[例8. Watching Fireworks is Fun (CF 372 C)](https://codeforces.com/problemset/problem/372/C)** **例9. 多重背包問題** $dp(i,j) = \max{dp(i-1, j-x)}$ $\displaystyle dp(i,j) = \lfloor\frac{j}{w_i}\rfloor \times v_i + \max_{0 \le \frac{j-k}{w_i}\le s_i, j \equiv k \pmod {w_i}}\{dp(i-1,k) - \lfloor\frac{k}{w_i}\rfloor \times v_i\}$ ### 斜率優化 (?) 參考資料：https://codeforces.com/blog/entry/8219 參考資料：https://tioj.ck.tp.edu.tw/uploads/attachment/5/27/5.pdf $1D/1D$ 優化 $\displaystyle dp(i) = c_i + \max_{j \le R_i}\{a_jx_i + b_j\}$ 找最大的 $a_jx_i + b_j \rightarrow$ 當成 $y = a_jx_i + b_j$ 的直線 $\rightarrow$ 找凸包 (Convex Hull Optimization) 均攤分析：$\mathcal{O}(N \lg N)$ **[例10. Commando (APIO 2010)](http://www.codah.club/tasks.php?show_task=5000001044)** $\displaystyle \begin{array}{rtl} dp(i) & = \max_{j<i}\{dp(j)+a(S_i-S_j)^2 + b(S_i-S_j) + c\}\\ & = \max_{j<i}\{dp(j) + aS_i^2 + aS_j^2 - 2aS_iS_j + bS_i - bS_j + c\}\\ & = \max_{j<i}\{-2aS_jS_i + dp(j) + aS_i^2 + aS_j^2 - bS_j\} + aS_i^2 + bS_i + c\\ \end{array}$ - 單調過期 ### 分治優化 (?) **例11. 二維函數各點極值** **[例12. Yakiniku Restaurants (AtCoder arc067 F)](https://atcoder.jp/contests/arc067/tasks/arc067_d)** 證明凸四邊形不等式 $F(l_1,r_1) + F(l_2,r_2) \ge F(l_1,r_2) + F(l_2,r_1)$ ``` Solve(L, R, L', R') { if (L > R) return; M = (L + R) / 2; M' = L'; for (i = L'; i <= min(R', M); ++i) { if (F(i, M) > F(M', M)) M' = i; } Solve(L, M - 1, L', M'); Solve(M + 1, R, M', R); } ``` $\mathcal{O}(nm \lg n)$ ### Aliens 優化 (WQS 二分搜) (?) 參考資料：https://codeforces.com/blog/entry/49691 參考資料：https://tioj.ck.tp.edu.tw/uploads/attachment/5/51/10.pdf **例13. Utilitarianism** **例14. 凹函數求值** $M(p)$ 為 $f(x) - px$ 的最大值 $V(p)$ 為最大值發生的位置 - 內插法 $f(K) = f(V(p)) + \frac{f(V(p+1)) - f(V(p))}{V(p+1) - V(p)}(K - V(p))$ - 直接求 **[例15. Aliens (IOI 2016)](https://tioj.ck.tp.edu.tw/problems/1961)** ## Graph 定義 (on DFS Tree)： - 樹邊 - 回邊 - 前向邊 - 交錯邊定義： - 點 $k$ 連通：移除任意 $k-1$ 個點圖仍連通 - 邊 $k$ 連通：移除任意 $k-1$ 條邊圖仍連通判斷邊雙聯通 $\rightarrow$ 找橋判斷點雙聯通 $\rightarrow$ 找割點 ### Tarjan (?) - Robbin's Theorem ```cpp= void TarjanDFS(int v, int p) { stk.push(v); vis[v] = true; low[v] = dep[v] = ~p ? depth[p] + 1 : 0; for (int u : g[v]) { if (u == p) continue; if (vis[u]) { low[v] = min(low[v], dep[u]); } else { TarjanDFS(u, v); low[v] = min(low[v], low[u]); } } if (low[v] == dep[v]) { // the edge )v, p_ is a bridge if v is not the root vertex while (!stk.empty()) { int x = stk.top(); stk.pop(); bcc[x] = nbcc; if (x == v) break; } ++nbcc; } } ``` ### 縮點把連通分量縮成一點，只剩下橋 $\rightarrow$ 圖變成一棵樹。邊雙連通分量：樹點雙連通分量：圓方樹 ### 最近公共祖先 LCA 1. 跳到一樣的深度 2. 一層一層跳上去每次查詢需耗時 $\mathcal{O}(N)$，考慮以倍增法加速：存下所有節點 $2^k$ 的祖先，便可以以 $\mathcal{O}(\lg N)$ 時間完成步驟 (1), (2)。 > $p(v, 2^k) = p(p(v, 2^{k-1}), 2^{k-1})$ ```cpp= int LCA(int u, int v) { if (dep[u] > dep[v]) swap(u, v); for (int i = 0; i < kLog; ++i) { // if the i-th bit of (dep[v] - dep[u]) is 1 if (dep[v] - dep[u] >> i & 1) v = fa[v][i]; } if (u == v) return u; // special case for (int i = kLog-1; i >= 0; --i) { if (fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; } } // one step away from the LCA return fa[u][0]; } ``` ### 樹壓平紀錄 DFS 時進入離開時間，同一子樹內編號必定連續，可以做子樹修改、子樹和。 ### 樹上尤拉回路 (?) 可以用 RMQ 加速至 $\mathcal{O}(\lg N)$ 預處理，$\mathcal{O}(1)$ 查詢。 ### 樹鍊剖分樹壓平的時候，同一子樹內編號必定連續，但路徑不會連續。這時，需要選取一個恰當的順序 DFS，即可以保證同一條樹鍊在壓平後的編號連續，即可以以資料結構維護。輕重鍊剖分：優先 DFS 子樹較大的子樹，保證任意點跳到根只會經過 $\le \lg N$ 條樹鍊。若區間詢問複雜度 $\mathcal{O}(\lg N)$，則整體複雜度 $\mathcal{O}(\lg^2N)$。 ### 重心剖分 (?) 定義：一個節點 $v$ 被稱為重心 (centroid) 若移除 $v$ 之後最大連通塊的大小 $\le \lfloor \frac{N}{2} \rfloor$。重心分治：計算所有會經過重心的答案，移除重心後，進入各子樹遞迴。 $\displaystyle T(N) = \sum{T(s_i)} + f(N)$ 重心樹：構造出一棵相關的(?) 樹使深度 $\le \lg N$，會破壞部分原本樹上的邊。構造法：選擇重心，遞迴找到子樹的重心並連邊。構造時間 $\mathcal{O}(N \lg N)$。如何尋找重心？ ### 樹 DP (?) ### 全方位木 DP (?)