---
tags: 2024-i2cp

type: slide

slideOptions:
transition: fade;

---

<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>

# DP (單調隊列 區間DP 數位DP)

Introduction to Competitive Programming
04/03

---

## 上課內容

- 單調隊列
* 單調隊列介紹
* 多重背包優化
- 區間DP
- 數位DP

---

## 單調隊列優化

[例題](https://zerojudge.tw/ShowProblem?problemid=c528)：
給定一整數陣列，求取出數字的總和最大，且滿足相鄰兩數距離不能超過 $k$

----

定義狀態：
$$dp[i]=\mbox{從頭開始選到 $i$ 且有選 $i$ 的最大值}$$
狀態轉移：
$$dp[i] = arr[i] + max\{dp[i-1], dp[i-2], \dots, dp[i-k], 0\}$$

----

### 方法一：
$max\{dp[i-k], \dots, dp[i-3], dp[i-2], dp[i-1]\}$

相當於求區間最大值，砸線段樹！
複雜度 $O(N\log N)$

----

### 方法二：
$max\{dp[i-k], \dots, dp[i-3], dp[i-2], dp[i-1]\}$

如果 $a < b$ 且 $dp[a] < dp[b]$，那 $dp[a]$ 就再也用不到了
我們將 $(dp[x], x)$ 存入 deque

$k = 7$ ，維護 $dp[4] \sim dp[10]$
$[(8, 4), (3, 5), (5, 6), (7, 7), (6, 8), (1, 9), (2, 10)]$
把沒用的拿掉會變成
$[(8, 4), (7, 7), (6, 8), (2, 10)]$

讓 deque 保持單調遞減

----

現在要計算 $dp[11]$
$dp[11] = 8 + arr[i] = 5$ (假設)

從右邊塞入 $(dp[11], 11)$ 把比 $dp[11]$ 小的 pop 掉
$[(8, 4), (7, 7), (6, 8), (2, 10)]$
-> $[(8, 4), (7, 7), (6, 8), (5, 11)]$

在求 $dp[12]$ 之前我們檢查 deque 的最左邊的元素離 $12$ 有沒有超過 $k$
小於 $12 - k$ 的話要 pop 掉
-> $[(7, 7), (6, 8), (5, 11)]$

----

複雜度：
轉移只需要 $O(1)$ 取出 deque 的頭部
每個元素最多只會被 push 一次 pop 一次
所以總複雜度是 $O(N)$

----

範例 code
(std::deque 很肥最好用其它東西代替)

vector<pair<int, int>> deq(n + 5);
int l = 0, r = 0;
deq[l] = {0, 0};
for (int i = 1; i <= n; i++) {
    while (deq[l].second < i - k) l++;
    dp[i] = deq[l].first + arr[i];
    while (l <= r and deq[r].first <= dp[i]) r--;
    deq[++r] = {dp[i], i}
}

----

## 單調隊列優化背包問題
有 $N$ 種物品，價值、重量、個數分別是 $v_i, w_i, t_i$ ，和負重 $M$ 的背包，求最大值。

----

### 方法一：
把 $t_i$ 個相同物品當成 $t_i$ 不同物品作 $0/1$ 背包
複雜度：$O(M \sum t_i)$

----

### 方法二：
其實不需要 $t_i$ 個物品那麼多，假設 $t_i=15=1111_{(2)}$，把 $t_i$個物品分成 四組分別有 $1, 2, 2^2, 2^3$ 個物品，這些物品可以組合成 $0 \sim 15$ 。如果 $t_i$ 不是 $2^p - 1$ ， 我們可以先取 $q$ 個，讓 $t_i - q = 2^p - 1$ ，把 $t_i 分解成 {1, 2, \dots, 2^{p-1}, q}$

複雜度：$O(M \sum \log t_i)$

----

### 方法三：
觀察轉移式

$$dp[i][j] = \max_{k=0\sim t_i}\{ dp[i-1][j-k*w[i]]+k*v[i] \}$$

$$ = \max_{k=0\sim t_i}\{ dp[i-1][j-k*w[i]]-\lfloor\frac{j-k*w[i]}{w[i]}\rfloor*v[i]\}+\lfloor\frac{j}{w[i]}\rfloor * v[i]$$

我們令 $F[t] = dp[i-1][t] + \lfloor \frac{t}{w[i]} \rfloor*v[i]$，轉移式就可以寫成

$$ dp[i][j] = \max_{k=j, j-w[i],\dots j-w[i]*t[i]}\{F[k]\}+\lfloor \frac{j}{w[i]} \rfloor * v[i] $$

這樣就可以把 $(F[i], i)$ 丟進 deque 維護單調性

----

對每個物品 $i$ ，分別對所有除 $w[i]$ 有相同餘數的 $index$ 做單調隊列優化 DP ，一共做 $w[i]$ 次，複雜度是 $O(MN)$ 。

---

## 區間DP

- 區間 $dp$ 就是定義 $dp[l][r]=$ $l\sim r$ 的最優解。

- 問題會有合併這個動作，所以子結構會被分成 $l\sim k$ 和 $k+1\sim r$。

- 通常會是 $O(n^2)$ 的狀態加上 $O(n)$ 轉移
常見的範圍：$n \le 200, 300, 500$

----

矩陣鏈乘積：
$r\times h$ 的矩陣乘 $h \times c$ 的矩陣需要 $r\times c\times h$ 次運算。現在有 $n$ 個矩陣 $A_1A_2\cdots A_n$ 要相乘，求最少需要幾次運算

- $A_i$ 是 $r_i \times c_i$ 的矩陣，且 $c_i=r_{i+1},i=1\sim n-1$

$((A_1(A_2A_3))A_4)$
$((A_1A_2)(A_3A_4))$
$(((A_1A_2)A_3)A_4)$
$\cdots$

----

$dp[l][r]=$ 計算 $A_lA_{l+1}...A_{r-1}A_{r}$ 的最少運算次數
$dp[1][5]$ 的子問題：
$(A_1)(A_2A_3A_4A_5) \implies (dp[1][1])(dp[2][5])$
$(A_1A_2)(A_3A_4A_5) \implies (dp[1][2])(dp[3][5])$
$(A_1A_2A_3)(A_4A_5) \implies (dp[1][3])(dp[4][5])$
$(A_1A_2A_3A_4)(A_5) \implies (dp[1][4])(dp[5][5])$

----

轉移式：$$dp[l][r] = \min_{k=l\sim r-1}\{dp[l][k]+n_im_km_r+dp[k+1][r]\}$$ 狀態有 $O(n^2) 個$ ，轉移需要 $O(n)$ ，複雜度是 $O(n^3)$
按照區間長度由小到大計算 $dp$

----

code

for (int i = 1; i <= n; i++) dp[i][i] = 0 // 區間大小為 1 為 base case
for (int len = 2; len <= n; len++) // 由小區間往大開始轉移
    for (int l = 1, r = len; r <= n; l++, r++) {
        dp[l][r] = INF;
        for (int k = l; k < r; k++)
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + n[i]*m[k]*n[r]);
    }
return dp[1][n];

----

[P1880 [NOI1995] 石子合并：](https://www.luogu.com.cn/problem/P1880)

有 $n$ 堆石頭擺成 $\textbf{一圈}$，石頭的數量分別是 $a_1 \sim a_n$ ，每次可以合併相鄰的兩堆石頭，獲得的分數是這堆石頭的個數，問把所有石頭變成一堆的最大得分和最小得分

- $1 \le n \le 100, 0 \le a_i \le 20$

----

先考慮更簡單的問題，$n$ 堆石頭擺成 "一排" 的情況

$dp[l][r] =$ 把 $l\sim r$ 合併成一堆的最小分數
在 $l\sim r$ 合併成一堆之前他原本是兩堆，這兩堆一定分別是 $l\sim k$ 堆出來的和 $k+1\sim r$ 堆出來的，所以轉移式是
$$dp[l][r] = \min_{k=l\sim r-1}\{dp[l][k]+dp[k+1][r]+sum[l][k]+sum[k+1][r]\}$$

$$= \min_{k=l\sim r-1}\{dp[l][k]+dp[k+1][r]\}+sum[l][r]$$

複雜度 $O(n^3)$

----

現在考慮原問題，在把一圈石頭合併成一堆之前他是兩堆石頭，這兩堆石頭是怎麼來的？

以 $n=7$ 為例
如果最優解是由 $1\sim4$ 和 $5\sim7$ 兩堆而來的，那 $dp[1][7]$ 可以計算到它

----

可是如果是這樣的話 $dp[1][7]$ 就算不到它了
但是我們可以把原序列 $a_1, a_2, a_3,\cdots ,a_7$，透過旋轉擺成 $a_3, a_4, \cdots a_7, a_1, a_2$，再去算 $dp$ ，這時候 $dp[1][7]$ 就可以從由這兩堆轉移而來

----

因為我們不知道最優解長怎樣，所以要把
$a_1, a_2, a_3, a_4, a_5, a_6, a_7$,
$a_7, a_1, a_2, a_3, a_4, a_5, a_6$,
$a_6, a_7, a_1, a_2, a_3, a_4, a_5$,
$\cdots$
都算一遍然後取最優的那個 $dp[1][7]$，
因為要做 $n$ 次 $dp$ 所以複雜度是 $O(n^4)$

----

我們不需要每次旋轉一格然後從算，直接把原序列複製一遍接在後面變成
$a_1, a_2, a_3, a_4, a_5, a_6, a_7,$ $a_1, a_2, a_3, a_4, a_5, a_6, a_7$
再去算長度為 $2n$ 的 $dp$，最後取 $dp[1][7], dp[2][8], dp[3][9], \cdots, dp[7][13]$ 的最小值，複雜度還是 $O(n^3)$

----

[CF1132F Clear the String](https://codeforces.com/problemset/problem/1132/F)

給一個長度為 $n$ 由 $a\sim z$ 組成的字串 $s$，每次操作可以刪除 $s$ 中有連續相同字元的區間，問最少要幾次操作才能把 $s$ 全部消掉

- $1 \le n=|s| \le 500$

----

這種消掉一個區間然後再合併的區間消除問題很常見，它有兩個很重要的性質。

1. 連續一樣的東西一定是一起消掉，沒理由分開消
以這題來說，顯然

2. 最左邊或是最右邊的連通塊一定可以留到最後消
以最左邊為例，先消掉最左邊不會影響它右邊的部分，因為它的左邊沒有東西跟右邊合併，所以把最左邊留下先把右邊的部分消完也不影響答案

----

- 由 1. 我們可以把原字串連續一樣的部分直接變成 $($什麼字元, 有幾個$)$

- 由 2. 我們可以定義 $dp[l][r]=$ 把 $s[l:r]$ ， 消到剩下(不知道幾個) $s[l]$ 需要多少次操作

----

轉移：
$s[l:r]$ 消成一堆 $s[l]$ 可以
- 直接把 $s[l+1:r]$ 消掉留下 $s[l]$
$dp[l][r] = dp[l+1][r] + 1$

- $s[l]$ 最後跟 $s[k]$ 合併
$s[l]=s[k]$
要把 $s[l, k-1]$ 消成 $s[l]$，$s[k:r]$ 消成 $s[k]$
$dp[l][r] = dp[l][k-1] + dp[k][r]$

- $s[l]$ 最後跟 $s[k], s[k_1], s[k_2], \cdots$ 合併？
不用考慮那麼多，如果跟 $s[k_1], s[k_2]\cdots$ 併會比較好的話，會在把 $s[k:r]$ 變成一堆 $s[k]$ 的時候合併，$dp[k][r]$ 已經幫我們處理好了。

----

$$dp[l][r]=min(dp[l+1][r]+1, \min_{k=l+1\sim r}\{dp[l][k-1]+dp[k][r]\})$$

答案是 $dp[1][n]+1$ 因為要再花一次操作把 $s[1]$ 消掉。
複雜度：$O(n^3)$

----

code

for (int i = 1; i <= n; i++) dp[i][i] = 0;
	for (int len = 2; len <= n; len++)
		for (int l = 1, r = len; r <= n; l++, r++) {
			dp[l][r] = 1 + dp[l+1][r];
			for (int k = l+1; k <= r; k++)
				if (S[l] == S[k])
					dp[l][r] = min(dp[l][r], dp[l][k-1] + dp[k][r]);
		}
return dp[1][n] + 1;

----

[2020 ICPC 台灣站 pE](https://codeforces.com/gym/102835/problem/E)

給一個由 R, G, B, C, M, Y, K 七種字元組成的字串 $s$ ，每次可以把長度 $\ge m$ 的相同字元的子字串消掉，問能不能把 $s$ 全部消掉。
- $0 < n, m, \le 500$

----

- 由 1. 先把 $s$ 連續相同的部分合併，變成 $($什麼字元, 有幾個$)$

- 由 2. 定義 $dp[l][r]=$ 能把 $s[l:r]$ 消成 "最多幾個" $s[l]$，或是沒辦法 $0$
如果能把 $s[l:r]$ 全部消掉的話，把最左邊那塊留到最後，等於 $s[l]$ 的這塊最後可能直接消掉或是跟別人合併，不管是哪種一定是越大越好。

----

轉移：
$s[l:r]$ 消成一堆 $s[l]$ 可以

- 直接把 $s[l+1:r]$ 消掉留下 $s[l]$
要判斷 $s[l+1:r]$ 能不能被消掉，也就是 $dp[l+1][r] \ge m$
$dp[l][r] = dp[l][l]$

- $s[l]$ 最後跟 $s[k]$ 合併
$s[l]=s[k]$
要判斷能不能把 $s[l:k-1]$ 消成 $s[l]$，和 $s[k:r]$ 消成 $s[k]$
也就是 $dp[l][k-1] > 0\ \mbox{and}\ dp[k][r] > 0$
$dp[l][r] = dp[l][k-1] + dp[k][r]$

- $s[l]$ 最後跟 $s[k], s[k_1], s[k_2], \cdots$ 合併？
不用考慮那麼多...

----

跟上一題差不多，直接放code

for (int i = 1; i <= n; i++) dp[i][i] = cnt[i];
for (int len = 2; len <= n; len++)
    for (int l = 1, r = len; r <= n; l++, r++) {
        if (dp[l+1][r] >= m) dp[l][r] = dp[l][l];
        for (int k = l+1; k <= r; k++)
            if (s[l] == s[k] and dp[l][k-1] and dp[k][r])
                dp[l][r] = max(dp[l][r], dp[l][k-1] + dp[k][r]);
    }
return dp[1][n] >= m;

---

## 數位 DP

數位是指個、十、百、千等等一位一位地拆開，通常是拆十進位數$(0\sim 9)$或二進位數$(0,1)$

問在 $[L, R]$ 之間滿足某些條件的數有幾個，$L,R$ 的範圍通常可以到 $10^{18}$ 或是 $2000 \sim 5000$ 位數，條件會跟位數或是數值有關。

----

[例題1](https://cses.fi/problemset/task/2220)：
給你 $a, b$ 兩個數字，問 $a\sim b$ 沒有連續兩位相同的數有幾個

- $0 \le a \le b \le 10^{18}$

----

問題的答案是 $ans_{[L,R]}$，我們可以拆成 $ans_{[0,R]}-ans_{[0,L-1]}$，問題變成求 $0\sim S$ 有幾個滿足條件的數

記 $S[i]$ 表示 $S$ 從左往右看的第 $i$ 位，可以把 $S$ 想像成字串
從最高位開始放數字，現在要放第 $i$ 位，要滿足兩個條件
- 不能跟前一位 $S[i-1]$ 相同
- 不能超過 $S$
如果前面已經有一位 $j$ 滿足 $x[j] < S[j]$ 後面不管怎麼放都不會超過 $K$，如果前面個位數都跟 $S$ 一樣，那目前要放的這一位不能超過 $S[i]$

----

我們需要知道兩個資訊，前面個位數是不是貼著 $S$ 或已經小於 $S$，和前一位數是什麼，所以我們定義

$dp[i][j][0]=$ 第 $i$ 位是 $j$，且前 $i$ 位小於/等於(0/1) $S$ 的前 $i$ 位，且滿足條件的數有幾個
最後的答案是 $\sum dp[|S|-1][0\sim 9][0/1]$

----

用 push 的方式轉移
- $dp[i][j][0]$ 已經不用關心大小了，只要和 $j$ 不一樣就好

for $k=0\sim 9 \land k \ne j$
$dp[i+1][k][0] \mathrel{+}= dp[i][j][0]$

- $dp[i][j][1]$ 除了不能跟 $j$ 一樣還不能超過 $S[i+1]$

if $S[i+1] \ne j$
$dp[i+1][S[i+1]][1] \mathrel{+}= dp[i][j][1]$
for $k = 0\sim S[i+1]-1 \land k \ne j$
$dp[i+1][k][0] \mathrel{+}= dp[i][j][1]$

----

狀態數： $O(|S|\times 10 \times 2)$
轉移數：$O(10)$
複雜度 $O(10\times 10\times 2\times |S|)=O(位數)$

----

code

long long l, r;
cin >> l >> r;

auto DP = [&](long long x) -> long long {
    if (x == -1) return 0;
    vector<int> s;
    for (char c : to_string(x))	s.emplace_back(c - '0');
    const int n = s.size();
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= s[0]; i++) dp[0][i][i == s[0]] = 1;
    for (int i = 0; i+1 < n; i++) {
        dp[i][0][0]++;
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < 10; k++) {
                if (k == j) continue;
                if (k < s[i+1]) dp[i+1][k][0] += dp[i][j][1];
                if (k == s[i+1]) dp[i+1][k][1] += dp[i][j][1];
                dp[i+1][k][0] += dp[i][j][0];
            }
        }
    }
    long long ans = 1;
    for (int i = 0; i < 10; i++) ans += dp[n-1][i][0] + dp[n-1][i][1];
    return ans;
};

cout << DP(r) - DP(l-1) << '\n';

----

[例題2：](https://atcoder.jp/contests/dp/tasks/dp_s)

計算 $1\sim K$ 中有幾個數滿足以下條件，輸出 $\mbox{mod } 10^9+7$ 後的結果
- 所有位數的總和是 $D$ 的倍數

- $1 \le K < 10^{10000}$
- $1 \le D \le 100$

----

這次我們不需要紀錄上一位放什麼，但是要記錄目前的位數和是多少，我們最後只關心他是不是 $D$ 的倍數，所以定義狀態為

$dp[i][j][0] =$ 前 $i$ 位的位數和 $\% D$ 為 $j$，且前 $i$ 位小於/等於(0/1) K 的前 $i$ 位的數有幾個
答案是 $dp[|K|-1][0][0]+dp[|K|-1][0][1]$

----

轉移：
這裡一樣用 push 的
- $dp[i][j][0]$ 後面可以放任合數
for $k=1\sim 9:$
$dp[i+1][(j+k)\%D][0] \mathrel{+}= dp[i][j][0]$

- $dp[i][j][1]$ 後面不能放超過 $K[i+1]$ 的數
for $k=1\sim K[i+1]$
$dp[i+1][(j+k)\%D][k==K[i+1]] \mathrel{+}= dp[i][j][1]$

複雜度：$O(Dlog_{10}K)$

----

code

	for (int i = 0; i <= s[0]; i++) dp[0][i%d][i == s[0]] += 1;
	for (int i = 0; i + 1 < n; i++) {
		for (int j = 0; j < d; j++)
			for (int k = 0; k < 10; k++) {
				if (k <= s[i+1])
					(dp[i+1][(j+k)%d][k == s[i+1]] += dp[i][j][1]) %= mod;
				(dp[i+1][(j+k)%d][0] += dp[i][j][0]) %= mod;
			}
	}

	cout << (dp[n-1][0][0] + dp[n-1][0][1] + mod - 1) % mod << '\n';

---

### Homework and Practice