---
# System prepended metadata

title: IOICamp Day1 下午 - 動態規劃 & 圖論
tags: [IOICamp]

---

---
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 (?)




<!-- <style>
.mathjax .mjx-chtml {
    overflow-x: auto;
    overflow-y: hidden;
    max-width: 100%;
}
</style> -->