# 優質題單

# DP Time

:coffee::coffee::coffee::coffee::coffee:

:coffee::coffee::coffee::coffee::coffee:

:tea::tea::tea::tea::tea:

優質DP入門講義：[[SA's DP]](https://hackmd.io/@sa072686/DP)

:tea::tea::tea::tea::tea:

---

## 前言

DP Time 是 DP 題單，這個題單的題目都是**樸素**DP。
樸素的意思是理論上不需要帶優化就可以解的出來了
(但是 LIS 的 BIT 太經典了)

---

## 0.1 看到DP怎麼下手

我也想知道QQ

## 0.2 線性DP

什麼叫做線性DP呢？其實就是最基本的DP
沒有特別分出來的東西都叫線性DP
所以說線性DP可能是遞推or遞迴or多維or其他阿撒布魯的
通常是簡單題( 難題也很多就是了(x )，但是不一定會直接裸裸的出現在題目裡
有時候會是在解題的過程中的一小部分
(如果硬要說的話前綴和也算一種DP(x 所以說前綴和也很重要 dayo!)

因為我相信你們都很會DP了，所以說我這邊就不負責任的不放題目了...(x
雖然我很想這麼說，但是練好線性DP才是進入後面恐怖東西的第一步
所以來刷題囉(以下題目可能有按難度分，沒有提示，就是大雜燴)

1. [[LG 1077]](https://www.luogu.com.cn/problem/P1077)
2. [[LG 1541]](https://www.luogu.com.cn/problem/P1541)
3. [[LG 4059]](https://www.luogu.com.cn/problem/P4059)
4. [[CF 118D]](https://codeforces.com/problemset/problem/118/D)
5. [[CF 607A]](https://codeforces.com/problemset/problem/607/A)
6. [[UVA 1347]](https://vjudge.net/problem/UVA-1347) 經典題：兩相異路徑最短路

因為線性DP太多了，我隨便選幾題看起來不錯的就丟上來了
CF題來源大部分是這個題單 [[DP Practice]](https://vjudge.net/contest/424603)

## 1. LIS と LCS

### LIS 什麼的最喜歡了 >//<

LIS 就是一個二維偏序問題，套個 BIT 可以解決很多問題
但是也別忘記 LIS 原本的 DP 式了

1. [[N維偏序]](http://domen111.github.io/UVa-Easy-Viewer/?103)
2. [[LIS變形1]](https://ac.nowcoder.com/acm/contest/11164/D?&headNav=acm)
3. [[LIS變形2]](https://codeforces.com/problemset/problem/1468/A)
4. [[LIS變形3]](https://codeforces.com/group/zrTK4HK8Ew/contest/296734/problem/A) (未解)

### LCS 什麼的最討厭了 OAO

1. [[LCS變形1]](https://atcoder.jp/contests/abc130/tasks/abc130_e)

### 聽說 LCS 可以轉 LIS ?

什麼意思? Almost 裸題 是一個 LIS
如果我把 $x$ 座標換成 $a_i$， $y$ 座標換成 $b_i$
求 LCS 就變成跟那題求的東西一樣了 $\therefore LCS == LIS$

什麼時候可以用? 只需要輸出長度的時候
你說建圖也要 $NM$？數字小的時候可以Counting sort。數字大？離散化

複雜度？$O(Klog(min(N,M)) + R)$ 。$K$是數對數目， $N$ 和 $M$ 是序列長度，$R$是數字範圍。

最差情況下比 $O(NM)$ 還糟，但大部分時間快一點。$K$ 越小時可以用

1. [[UVA 10635]](https://vjudge.net/problem/UVA-10635)

---

## 2. 二維 DP

這邊的二維DP是在二維的平面上做DP，不是說狀態只有二維

1. 還有很多但是我懶得找了，Atcoder上很多好題

---

## 3. 背包 DP

背包博大精深，千萬不要覺得他很簡單，難死

簡單分類：

* 0/1 背包
* 無限背包
* 有限背包
* 分組背包
* 樹上背包

先上裸題

* 樹上背包 先等等 樹DP那邊再來

要注意的幾件事：

1. 背包是DP，不要硬套
2. 無限背包沒想好就會變成有限背包，要小心
3. 應該還有 但是我想不到

例題：
1. [[CF 336C]](https://codeforces.com/problemset/problem/366/C)
2. [[LG 1954]](https://www.luogu.com.cn/problem/P1941)
3. [[LG 1858]](https://www.luogu.com.cn/problem/P1858) 01背包前 $k$ 優解的價值和
4. [[CF 864E]](https://codeforces.com/problemset/problem/864/E) (未解)

## 4. 區間DP

在區間上做DP，通常複雜度都是 $N^2,N^3$
有時候可以搭配莫名其妙的四邊形優化

**用遞迴寫會異常好寫**

先來一些簡單經典題暖身

再來一些比較難一點點的經典好題
1. [[105全國賽pD變化]](https://vjudge.net/contest/400091#problem/H)
2. [[CF149D]](https://codeforces.com/problemset/problem/149/D) 特殊的轉移方式
3. [[IOI1998]Polygon](https://www.luogu.com.cn/problem/P4342) (未解)
4. [[顏色消除1]](https://codeforces.com/gym/102835/problem/E)
5. [[顏色消除2]](https://vjudge.net/problem/UVA-10559) (未解)

## 5. 環狀DP

如果解完石子合併的話你們應該學到了一個斷環成鍊的技巧了
但那個通常只有在區間DP可以用

正常的環狀DP作法是這樣子的：看哪裡有環，找環上一個點，枚舉他的所有Case，然後他就變成鍊了

環狀DP只是一個概念(技巧)而已，他不常裸裸的出現，所以說不放題目囉 OuO

其實是我懶(誤

## 6. 狀壓DP(位元DP)

貌似有人叫他位元DP，不要跟數位DP搞混了喔

### 6-1 $O(2^n)$

狀壓DP很常拿來把原本是 $N!$ 的複雜度壓成 $2^N$

大部分的做法就是用一個整數來表示一個狀態
令 $cnt(mask)$ = $mask$ 中 $1$ 的數量
最常見的手法是 $dp(mask)$ 代表前 $cnt(mask)$ 個人狀態是 $mask$ 的答案

上題目囉~
1. [[LG 2704]](https://www.luogu.com.cn/problem/P2704) 題目簡單但細節頗多
2. [[CF11D]](https://codeforces.com/problemset/problem/11/D)
### 6-2 $O(3^n)$ 枚舉子集的狀壓dp

這裡的 $3^n$ 不是指說用 $3$ 進制的整數存，一樣是二進制的整數當作狀態
最常見作法：先枚舉 $0\sim 2^n-1$，然後每一個再去做 dfs 枚舉子集
複雜度證明：$(2+1)^n=\sum\limits_{i=1}^{n}2^i\cdot$$n\choose i$

1. [[LG 3959]](https://www.luogu.com.cn/problem/P3959) 按層轉移
2. [[CF1209 E2]](https://codeforces.com/problemset/problem/1209/E2) (未解)

### 5-3. 輪廓線DP

這是一個困難的DP，我不太會，但是他蠻有趣的
他其實算是一種狀壓DP的分支，但又不完全是
1. [[CSES 2181]](https://cses.fi/problemset/task/2181)
## 6. 樹DP

這是一個恐怖的章節，因為我不會樹DP
樹DP比背包還要博大精深，他自己一個DP就延伸出很多分支了
但也因為這樣，他非常重要，可以說是DP的非常大個章節

主要有以下分支：

1. 普通DP
2. 樹上背包
3. 換根DP
4. 基環樹(只有一個環的樹)
5. 其他毒瘤(虛樹、長鍊剖分)

下面是一些 MISC 的題目，主要去看洛谷題單

1. [[好好寫就是 $O(n^2)$ 樹 dp]](https://acm.timus.ru/problem.aspx?space=1&num=1018)
2. [[TOI 2020 pB 推廣題]](https://codeforces.com/group/zrTK4HK8Ew/contest/296734/problem/C)

題單：[[洛谷樹DP]](https://www.luogu.com.cn/training/13994#problems)

---

###### tags: `校內培訓`

# 資料結構題單

## 自習資源

[CF edu](https://codeforces.com/edu/courses)

## 並查集 和 啟發式合併

[類似某次APCS第三題](https://cses.fi/problemset/task/1163)

[帶權並查集 二分圖](https://www.luogu.com.cn/problem/P1525)

這幾題都可以用 `擴展域` 和 `帶權並查集` 兩種方法來實作

[更多帶權並查集](https://www.luogu.com.cn/problem/P1196)

[更多掃描線](https://www.luogu.com.cn/problem/P1502)

[更多線段樹](https://cses.fi/problemset/task/2206)

Lazy Tag 在下傳的時候須考慮到各種狀況和先後順序非常重要

## 動態開點線段樹

[氣球博覽會](https://tioj.ck.tp.edu.tw/problems/1169)

全世界都會 就我不會 我弱

## 可持久化線段樹

[經典題 - 區間第k小](https://www.luogu.com.cn/problem/P3834)

[難題](https://codeforces.com/contest/484/problem/E)

[區間相異元素個數 變化題](https://codeforces.com/contest/813/problem/E)

[可持久化 + 合併 (未解)](https://codeforces.com/contest/893/problem/F)

## BIT

[有趣的一題](https://atcoder.jp/contests/abc201/tasks/abc201_f)

## 有趣應用

[線段樹優化建圖](https://codeforces.com/problemset/problem/786/B)

[線段樹優化建圖 + 網路流(未解)](https://codeforces.com/problemset/problem/793/G)

[線段樹 + 回滾並查集]電~(https://codeforces.com/contest/813/problem/F)