---
tags: Programming Contest
---
# Educational DP Contest 題解（A ~ M）
[題目連結](https://atcoder.jp/contests/dp)
## 心得
practice。
最近似乎遞推的寫法比較主流，所以我也嘗試用遞推來寫，而非我習慣的遞歸。
## A. [Frog 1](https://atcoder.jp/contests/dp/tasks/dp_a)
簡單 dp。
```python
N = int(input())
H = [int(x) for x in input().split()]
dp = [10 ** 10 for _ in range(N)]
dp[0] = 0
for i in range(N):
if i + 1 < N:
dp[i + 1] = min(dp[i + 1], dp[i] + abs(H[i + 1] - H[i]))
if i + 2 < N:
dp[i + 2] = min(dp[i + 2], dp[i] + abs(H[i + 2] - H[i]))
print(dp[N - 1])
```
## B. [Frog 2](https://atcoder.jp/contests/dp/tasks/dp_b)
簡單 dp。
```python
N, K = map(int, input().split())
H = [int(x) for x in input().split()]
dp = [10 ** 10 for _ in range(N)]
dp[0] = 0
for i in range(N):
for k in range(1, min(K + 1, N - i)):
dp[i + k] = min(dp[i + k], dp[i] + abs(H[i + k] - H[i]))
print(dp[N - 1])
```
## C. [Vacation](https://atcoder.jp/contests/dp/tasks/dp_c)
$dp[i, j]$ 為經過 $[0, i)$ 這些天，且第 $i - 1$ 天是活動 $j$ 的最大 happiness，然後照著題目的限制遞推。
```python
N = int(input())
# dp[i, j] = the maximum value of day [0, i), and perform j on day i - 1
dp = [[0, 0, 0] for _ in range(N + 1)]
dp[0] = [0, 0, 0]
for i in range(N):
gain = [int(x) for x in input().split()]
for j in range(3): # today
for k in range(3): # tomorrow
if j != k:
dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + gain[j])
print(max(dp[-1]))
```
## D. [Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)
經典 0/1 背包。
```python
N, W = map(int, input().split())
ws, vs = [], []
for _ in range(N):
w, v = map(int, input().split())
ws.append(w)
vs.append(v)
# dp[i, j] = maximum value while
# total weight is j and only [0, i) items are considered
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(N):
for j in range(W):
# don't use item i
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
# use item i
if j + ws[i] <= W:
dp[i + 1][j + ws[i]] = max(dp[i + 1][j + ws[i]], dp[i][j] + vs[i])
print(max(dp[N]))
```
## E. [Knapsack 2](https://atcoder.jp/contests/dp/tasks/dp_e)
還是 0/1 背包，但 $w_i$ 很大，$v_i$ 很小。
設 $dp[i, j]$ 為總價值為 $j$ 時，最小的物品重量和，只有物品 $[0, i)$ 有被考慮。
跟 0/1 背包一樣，考慮第 $i$ 件物品要用或不用，可以得到轉移方程。
最終結果為從大到小迭代總價值，看哪一個價值所需要的總重量在 $W$ 以內。
```python
N, W = map(int, input().split())
ws, vs = [], []
for _ in range(N):
w, v = map(int, input().split())
ws.append(w)
vs.append(v)
V = max(vs) * N
# dp[i, j] = minimum weight when
# total value is j and only items [0, i) are considered
INF = 10 ** 10
dp = [[INF for _ in range(V + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
for j in range(V + 1):
# don't use item i
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
# use item i
if j + vs[i] <= V:
dp[i + 1][j + vs[i]] = min(dp[i + 1][j + vs[i]], dp[i][j] + ws[i])
for v in range(V, -1, -1):
if dp[N][v] <= W:
print(v)
break
```
## F. [LCS](https://atcoder.jp/contests/dp/tasks/dp_f)
經典的 LCS。這題遞推實在不怎麼好寫，所以還是用標準遞歸的寫法。
實作上為了方便，我在 $S, T$ 的開頭補了 1 個相異的特殊字元。
```python
S = '#' + input()
T = '$' + input()
dp = [[0 for _ in range(len(T))] for _ in range(len(S))]
prev = [[-1 for _ in range(len(T))] for _ in range(len(S))]
for i in range(1, len(S)):
for j in range(1, len(T)):
if S[i] == T[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
prev[i][j] = 0
elif dp[i - 1][j] > dp[i][j - 1]:
dp[i][j] = dp[i - 1][j]
prev[i][j] = 1
else:
dp[i][j] = dp[i][j - 1]
prev[i][j] = 2
lcs = []
i, j = len(S) - 1, len(T) - 1
while i >= 0 and j >= 0:
if prev[i][j] == 0:
lcs.append(S[i])
i -= 1
j -= 1
elif prev[i][j] == 1:
i -= 1
elif prev[i][j] == 2:
j -= 1
else:
break
print(''.join(map(str, reversed(lcs))))
```
## G. [Longest Path](https://atcoder.jp/contests/dp/tasks/dp_g)
經典的 DAG 最長路徑。
設 $dp[v]$ 為停在 vertex $v$ 的所有路徑中，最長的長度。考慮 $v$ 的 incoming edges $E^-_v$，我們有：
$$
dp[v] = \max_{u \in E^-_v} dp[u] + 1
$$
根據轉移方程，可知這個 $dp$ 的計算順序為 DAG 的 topological order。
```python
from collections import deque
N, M = map(int, input().split())
in_deg = [0 for v in range(N)]
graph = [[] for v in range(N)]
for _ in range(M):
u, v = map(int, input().split())
u, v = u - 1, v - 1
graph[u].append(v)
in_deg[v] += 1
# dp[v] = length of the longest path ending at v
dp = [0 for _ in range(N)]
# topological order
que = deque([v for v, deg in enumerate(in_deg) if deg == 0])
while len(que) > 0:
u = que.popleft()
for v in graph[u]:
dp[v] = max(dp[v], dp[u] + 1)
in_deg[v] -= 1
if in_deg[v] == 0:
que.append(v)
print(max(dp))
```
## H. [Grid 1](https://atcoder.jp/contests/dp/tasks/dp_h)
這題一直出現一直出現……
設 $dp[r, c]$ 為從起點到 $(r, c)$ 的方法數。
```python
H, W = map(int, input().split())
A = [input() for _ in range(H)]
M = 10 ** 9 + 7
dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
for r in range(H):
for c in range(W):
if r + 1 < H and A[r + 1][c] == '.':
dp[r + 1][c] += dp[r][c]
dp[r + 1][c] %= M
if c + 1 < W and A[r][c + 1] == '.':
dp[r][c + 1] += dp[r][c]
dp[r][c + 1] %= M
print(dp[H - 1][W - 1])
```
## I. [Coins](https://atcoder.jp/contests/dp/tasks/dp_i)
給定 $N$ 個 coins，coin $i$ 得到 head 的機率是 $p_i$。依序拋完所有 coins，問得到「head 數量比 tail 多」的機率是多少？
設 $dp[i, j]$ 為拋完 coins $[0, i)$，head 的數量為 $j$ 的機率。考慮 coin i 的結果，得到轉移方程。
```python
N = int(input())
P = [float(x) for x in input().split()]
# dp[i][j] = Pr(number of head = j) after [0, i) coins are tossed
dp = [[0.0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0] = 1.0
for i in range(N):
for j in range(N + 1):
# coin i is tail
dp[i + 1][j] += dp[i][j] * (1 - P[i])
# coin i is head
if j + 1 <= N:
dp[i + 1][j + 1] += dp[i][j] * P[i]
ans = 0.0
for n_head in range(N + 1):
if n_head > N - n_head:
ans += dp[N][n_head]
print('{:.15f}'.format(ans))
```
## J. [Sushi](https://atcoder.jp/contests/dp/tasks/dp_j)
給定 N 個盤子，盤子 $i$ 上有壽司 $a_i$ 個。定義一次操作為 uniform 地選出一個盤子，若盤子上有壽司，吃掉其中一個。問吃完所有壽司的期望操作次數。
這題最重要的觀察是 **是哪一個盤子並不重要的，重要的是各種壽司數的盤子有幾個**，因為盤子是 uniform 地選。
設 $E(a, b, c)$ 為目前有 $a$ 個壽司數為 1 的盤子、 $b$ 個壽司數為 2 的盤子、 $c$ 個壽司數為 3 的盤子，將壽司吃完的期望操作次數。考慮接下來的一次操作，我們有
1. $\frac{a}{N}$ 的機率選到壽司數為 1 的盤子，吃掉一個壽司後，轉移到 $E(a - 1, b, c)$。
2. $\frac{b}{N}$ 的機率選到壽司數為 2 的盤子，吃掉一個壽司後，轉移到 $E(a + 1, b - 1, c)$。
3. $\frac{c}{N}$ 的機率選到壽司數為 3 的盤子，吃掉一個壽司後，轉移到 $E(a, b + 1, c - 1)$
4. $\frac{N - a - b - c}{N}$ 的機率選到壽司數為 0 的盤子，轉移到 $E(a, b, c)$。
數學式如下：
$$
\begin{align}
E(a, b, c) =
&1 +
\frac{a}{N} E(a - 1, b, c) +
\frac{b}{N} E(a + 1, b - 1, c) + \\
&\frac{c}{N} E(a, b + 1, c - 1) +
\frac{N - a - b - c}{N} E(a, b, c)
\end{align}
$$
整理後得轉移方程：
$$
E(a, b, c) = \frac{N}{a + b + c} \left(
1 +
\frac{a}{N} E(a - 1, b, c) +
\frac{b}{N} E(a + 1, b - 1, c) +
\frac{c}{N} E(a, b + 1, c - 1)
\right)
$$
實作上使用 top-down dp，這題用 python 時間會非常緊，建議使用 c++。
```cpp
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
using real = long double;
int N;
real dp[301][301][301];
real E(int a, int b, int c) {
if (dp[a][b][c] >= 0) {
return dp[a][b][c];
}
if (a == 0 && b == 0 && c == 0) {
dp[a][b][c] = 0;
return 0;
}
real res = 1;
if (a >= 1) res += real(a) / N * E(a - 1, b, c);
if (b >= 1) res += real(b) / N * E(a + 1, b - 1, c);
if (c >= 1) res += real(c) / N * E(a, b + 1, c - 1);
res *= real(N) / (a + b + c);
dp[a][b][c] = res;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
vector<int> cnt(4, 0);
for (int i = 0; i < N; i++) {
int a;
cin >> a;
cnt[a]++;
}
for (int i = 0; i <= 300; i++) {
for (int j = 0; j <= 300; j++) {
for (int k = 0; k <= 300; k++) {
dp[i][j][k] = -1.0;
}
}
}
cout << fixed << setprecision(10) << E(cnt[1], cnt[2], cnt[3]) << endl;
return 0;
}
```
## K. [Stones](https://atcoder.jp/contests/dp/tasks/dp_k)
給定 $N$ 個正整數 $A$，Tora 與 Jiro 輪流從 $K$ 個石頭中拿走一些，拿走的數量必需是 $A$ 中的一項。Tora 先拿，誰沒石頭拿誰就輸山，若雙方都是最優地拿，誰會贏？
$dp[i, j]$ = 若剩下 $i$ 個石頭，現在換 $j$（Tora = $0$, Jiro = $1$）拿，$j$ 會不會贏（win = True, lose = False）。
根據題意，$dp[0, 0] = dp[0, 1] = False$。讓我們考慮 $dp[i, 0]$ 什麼時候會是 True？是前一步的狀態中，有任何一個狀態 Jiro 是輸的！寫成式子：
```python
dp[i, 0] = True if any(dp[i - a, 1] is False for a in A) else False
```
同理，$dp[i, 1]$ 也有：
```python
dp[i, 1] = True if any(dp[i - a, 0] is False for a in A) else False
```
實作上小心邊界。這題用遞歸比遞推好懂。另外發現拿 tabulate 來印 dp 表格挺方便的。
```python
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
# dp[i][j] = True if j will win when it's j's turn and i stones remained
dp = [[-1, -1] for i in range(K + 1)]
dp[0][0] = False
dp[0][1] = False
for i in range(1, K + 1):
dp[i][0] = True if any(dp[i - a][1] is False for a in A if i - a >= 0) else False
dp[i][1] = True if any(dp[i - a][0] is False for a in A if i - a >= 0) else False
# from tabulate import tabulate
# print(tabulate(dp, showindex=True, headers=['Taro', 'Jiro']))
print('First' if dp[K][0] else 'Second')
```
## L. [Deque](https://atcoder.jp/contests/dp/tasks/dp_l)
給定長度為 $N$ 的 deque $A$，Taro 與 Jiro 輪流：拿走 $A$ 的開頭抑或結尾，直到 $A$ 被拿完。最終 Taro 拿走的數字和為 $X$，Jiro 是 $Y$。若 Taro 想要最大化 $X - Y$，Jiro 想要最小化 $X - Y$，問最後 $X - Y$ 是多少？
設 $f(i, j, k)$ 為只考慮 $A$ 的封閉區間 $[i, j]$ 且現在換 $k$ 拿 (Taro = 1, Jiro = 0），得到的 $X - Y$。
根據題意，枚舉 $k$ 能拿的 2 個數字，得到轉移方程：
$$
\begin{align}
f(i, j, 1) = max(f(i + 1, j) + A_i, f(i, j - 1) + A_j) \\
f(i, j, 0) = min(f(i + 1, j) - A_i, f(i, j - 1) - A_j)
\end{align}
$$
top-down dp，用 python 會 TLE。
```cpp
#include <iostream>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int N;
ll A[3000];
ll dp[3000][3000][2];
ll f(int i, int j, bool is_tora) {
if (dp[i][j][is_tora] != INF) {
return dp[i][j][is_tora];
}
ll res = 0;
if (i == j) {
res = (is_tora) ? A[i] : -A[i];
} else if (is_tora) {
res = max(f(i + 1, j, false) + A[i], f(i, j - 1, false) + A[j]);
} else {
res = min(f(i + 1, j, true) - A[i], f(i, j - 1, true) - A[j]);
}
dp[i][j][is_tora] = res;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dp[i][j][0] = INF;
dp[i][j][1] = INF;
}
}
cout << f(0, N - 1, true) << endl;
return 0;
}
```
## M. [Candies](https://atcoder.jp/contests/dp/tasks/dp_m)
將整數 $K$ 拆成 $N$ 個非負整數的和，且第 $i$ 個數 $x_i$ 滿足 $x_i \in [0, a_i]$。問方法數。
這題用遞推要優化似乎很難想，讓我們還是使用遞歸。
設 $dp[i, j]$ 為使用 $x_0, x_1, \cdots, x_i$ 組出 $j$ 的方法數，題目所求即為 $dp[N - 1, K]$。
考慮 $x_i$ 是多少：下界是 $0$，上界是 $min(a_i, j)$，我們得到轉移：
$$
dp[i, j]
= \sum_{k=0}^{min(a_i, j)} dp[i - 1, j - k]
= \sum_{k=j - min(a_i, j)}^j dp[i - 1, k]
= \sum_{k=max(0, j - a_i)}^j dp[i - 1, k]
$$
整體時間 $O(NK^2)$ 會 TLE。我們嘗試優化，發現右式就是之前 dp 值的某個區間和，因此如果我們使用 BIT/SegTree 來存 dp 表格，我們能將時間降至 $O(NKlgK)$：
```cpp
#include <atcoder/fenwicktree>
#include <atcoder/modint>
#include <iostream>
#include <vector>
using namespace std;
using mint = atcoder::modint1000000007;
using BIT = atcoder::fenwick_tree<mint>;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<int> A(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
}
auto dp = vector<BIT>(N, BIT(K + 1));
for (int j = 0; j <= A[0]; j++) {
dp[0].add(j, +1);
}
for (int i = 1; i < N; i++) {
for (int j = 0; j <= K; j++) {
dp[i].add(j, dp[i - 1].sum(j - min(A[i], j), j + 1));
}
}
cout << dp[N - 1].sum(K, K + 1).val() << endl;
return 0;
}
```
另外我們也可以仔細的觀察轉移的右式，會發現他基本上就是 $dp[i - 1]$ 中，$j$ 以左長度 $a_i$ 的 window 的和，超出邊界的部份不算，因此我們用一個變數 `window_sum` 去記錄這個和，`window_sum` 會隨著 $j$ 的迭代更新。
```python
N, K = map(int, input().split())
mod = 10 ** 9 + 7
A = [int(x) for x in input().split()]
dp = [[0 for _ in range(K + 1)] for _ in range(N)]
for j in range(A[0] + 1):
dp[0][j] = 1
for i in range(1, N):
window_sum = 0
for j in range(K + 1):
window_sum += dp[i - 1][j]
if j - A[i] - 1 >= 0:
window_sum -= dp[i - 1][j - A[i] - 1]
window_sum %= mod
dp[i][j] = window_sum
print(dp[N - 1][K])
```
:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::
Sign in with Wallet
Connect another wallet