我是 dp 菜雞
尚未完成，有時間就會補個題目。巨集們可以在 About 找到，程式碼只放實際有效部分。
Problem A - Frog 1#
定義 \(f_i\) 為走到第 \(i\) 個石頭時的最小成本。由於要走到第 \(i\) 階只能從第 \(i-1\) 或 \(i-2\) 階，因此轉移式如下
$$ f_i = \min (f_{i-1} + |h_i-h_{i-1}|, f_{i-2} + |h_i-h_{i-2}|) $$
AC code
int n, h[100005], dp[100005];
signed main() {
hyper;
cin >> n;
rep1(i,1,n) cin >> h[i];
dp[1] = 0, dp[2] = abs(h[2] - h[1]);
rep1(i,3,n) dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
cout << dp[n];
}
Problem B - Frog 2#
定義 \(f_i\) 為走到第 \(i\) 個石頭時的最小成本。轉移式如下
$$ f_i = \min_{j\in[1,k]} \{ f_{i-j} + |h_i-h_{i-j}| \} $$
因為有 \(k\) 種可能，直接跑迴圈轉移即可。
AC code
int n, k, h[100005], dp[100005];
signed main() {
hyper;
rr(dp,0x3f);
cin >> n >> k;
rep1(i,1,n) cin >> h[i];
dp[1] = 0;
rep1(i,2,n) rep1(j,1,k) {
if(i-j >= 0) dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]));
}
cout << dp[n];
}
Problem C - Vacation#
定義一個二維 dp，\(f_{i,j}\) 代表考慮第 \(1\) 到 \(j\) 天，且第 \(j\) 天選擇的是活動 \(i\in\{0,1,2\}\)。轉移式如下
$$ f_{0,j} = \max (f_{1,j-1} + b_j, f_{2,j-1} + c_j) $$
以此類推。
AC code
int n, a[3][MAXN], dp[3][MAXN];
signed main() {
hyper;
cin >> n;
rep1(i,1,n) rep(j,0,3) cin >> a[j][i];
rep1(i,1,n) {
dp[0][i] = max(dp[1][i-1]+a[1][i],dp[2][i-1]+a[2][i]);
dp[1][i] = max(dp[0][i-1]+a[0][i],dp[2][i-1]+a[2][i]);
dp[2][i] = max(dp[0][i-1]+a[0][i],dp[1][i-1]+a[1][i]);
}
cout << max(dp[0][n],max(dp[1][n],dp[2][n]));
}
Problem D - Knapsack 1#
沒有任何變化的 01 背包問題，就不寫題解了嘻嘻。
AC code
int n, m, dp[MAXW], w[MAXN], v[MAXN];
signed main() {
hyper;
cin >> n >> m;
rep1(i,1,n) cin >> w[i] >> v[i];
rep1(i,1,n) {
for(int j=m; j>=w[i]; --j) {
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}
}
cout << dp[m];
}
Problem E - Knapsack 2#
01 背包問題，但 \(W\) 太大了，所以換個方法定義，\(f_i\) 表示要裝總價值 \(i\) 的物品所需的最小容量，然後從價值大到小的開始找答案。
AC code
int n, m, dp[MAXW], w[MAXN], v[MAXN];
signed main() {
hyper;
cin >> n >> m;
rep1(i,1,n) cin >> w[i] >> v[i];
rr(dp,0x3f);
dp[0] = 0;
rep1(i,1,n) {
for(int j=100000; j>=v[i]; --j) {
dp[j] = min(dp[j], dp[j-v[i]]+w[i]);
}
}
for(int i=100000; i>=0; --i) {
if(dp[i] <= m) {
cout << i;
return 0;
}
}
}
Problem F - LCS#
LCS 板子題，dp 時記一下是從誰轉移過來，最後找答案就沿路回推。
AC code
string s, t;
int dp[3005][3005], pv[3005][3005];
void print(int i, int j) {
if(i==0 || j==0) return;
if(pv[i][j]==0) {
print(i-1, j-1);
cout << s[i-1];
}
else if(pv[i][j]==1) print(i-1, j);
else print(i, j-1);
}
signed main() {
hyper;
cin >> s >> t;
int ls = s.length(), lt = t.length();
rep1(i,1,ls) rep1(j,1,lt) {
if(s[i-1] == t[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
pv[i][j] = 0;
}
else if(dp[i-1][j] >= dp[i][j-1]) {
dp[i][j] = dp[i-1][j];
pv[i][j] = 1;
}
else {
dp[i][j] = dp[i][j-1];
pv[i][j] = 2;
}
}
print(ls, lt);
}
Problem G - Longest Path#
定義 \(f_i\) 表示以 \(i\) 為結尾的最長路徑長，並依照拓樸順序遍歷節點 \(u\)，如果存在邊 \(u \to v\)，就更新
$$ f_v \leftarrow \max \{ f_v, f_u + 1 \} $$
最後答案為 \(\max_{i \in V} f_i\)
AC code
int n, m, in[MAXN], dp[MAXN];
vector<int> g[MAXN];
signed main() {
hyper;
cin >> n >> m;
rep(i,0,m) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
in[y]++;
}
queue<int> q;
rep1(i,1,n) if(!in[i]) q.push(i);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int v: g[u]) {
dp[v] = max(dp[v], dp[u]+1);
if(!--in[v]) q.push(v);
}
}
cout << *max_element(dp+1, dp+1+n);
}
Problem H - Grid 1#
經典排組題。走到某一格的方法數就是走到他上面的方法數 + 走到他左邊的方法數，而不能走的格子方法數顯然是 \(0\)。定義 \(f_{i,j}\) 是走到座標 \((i,j)\) 格子的方法數，轉移式如下
$$ f_{i,j} = \begin{cases} 0, & (i,j)\text{ is wall} \\ f_{i-1,j}+f_{i,j-1}, & \text{else} \end{cases} $$
AC code
int h, w, dp[MAXN][MAXN];
string a[MAXN];
signed main() {
hyper;
cin >> h >> w;
rep(i,0,h) cin >> a[i];
rep(i,0,h) dp[i][0] = 0;
rep(i,0,w) dp[0][i] = 0;
dp[1][1] = 1;
rep1(i,1,h) rep1(j,1,w) {
if(i==1 && j==1) continue;
if(a[i-1][j-1] == '#') dp[i][j] = 0;
else dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
}
cout << dp[h][w];
}
Problem I - Coins#
機率 dp，跟高中數學題差不多。假設 \(f_{i, j}\) 表示有 \(i\) 個硬幣，其中 \(j\) 個是 head 的機率，那麼它可以從 \(i-1\) 個硬幣推得：
$$ f_{i, j} = f_{i-1, j-1} \times p_i + f_{i-1, j} \times (1 - p_i) $$
也就是考慮第 \(i\) 個是正面還是反面。注意處理邊界就好，時間複雜度是 \(O(n^2)\)。
AC code
int n;
double p[MAXN], dp[MAXN][MAXN];
signed main() {
hyper;
cin >> n;
rep1(i,1,n) cin >> p[i];
dp[0][0] = 1;
rep1(i,1,n) {
dp[i][0] = dp[i-1][0]*(1-p[i]);
rep1(j,1,i) dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1-p[i]);
}
double sum = 0;
for(int i=n; i>n-i; --i) sum += dp[n][i];
cout << fixed << setprecision(10) << sum;
}
Problem J - Sushi#
關鍵是盤子裡最多只會有 3 個壽司，而且因為隨機均勻分布，盤子的順序並不重要，所以我們可以用三個維度 \(x, y, z\) 分別表示剩餘 \(1, 2, 3\) 個壽司的盤子數量，空盤子數就是 \(n - x - y - z\)。令 \(f(x,y,z)\) 是盤子在此狀態下時的答案（吃光所需次數的期望值），不難推出：
$$ f(x,y,z) = \frac{1}{x+y+z} \left( n + x f(x-1,y,z) + y f(x+1,y-1,z) + z f(x,y+1,z-1) \right) $$
這邊使用遞迴 + 記憶化搜尋來寫（我也不知道為什麼當初這樣寫，不過這樣不用考慮計算順序），總之複雜度是 \(O(n^3)\) 稍微有點緊。
AC code
int n, cnt[4];
double dp[MAXN][MAXN][MAXN];
double sol(int x, int y, int z) {
if(x<0 || y<0 || z<0) return 0;
if(dp[x][y][z] >= 0) return dp[x][y][z];
return dp[x][y][z] = (n+x*sol(x-1,y,z)+y*sol(x+1,y-1,z)+z*sol(x,y+1,z-1))/(x+y+z);
}
signed main() {
hyper;
cin >> n;
rep1(i,1,n) {
int x;
cin >> x;
cnt[x]++;
}
rep1(i,0,n) rep1(j,0,n) rep1(k,0,n) dp[i][j][k] = -1;
dp[0][0][0] = 0;
cout << fixed << setprecision(10) << sol(cnt[1],cnt[2],cnt[3]);
}
Problem K - Stones#
一定必勝或必敗，定義 \(f_i\) 代表目前只有 \(i\) 顆石頭的情況下，先手是否獲勝。只要拿走任一種數量的石頭使得對手接下來必敗就贏了，否則就是輸。轉移式如下
$$ f_i = \begin{cases} 1, & \exists \, a_i : f_{i-a_i} = 0 \\ 0, & else \end{cases} $$
AC code
int n, k, a[105];
bool dp[100005];
signed main() {
hyper;
cin >> n >> k;
rep(i,0,n) cin >> a[i];
rep1(i,1,k) rep(j,0,n) {
if(i-a[j] >= 0 && !dp[i-a[j]]) dp[i] = 1;
}
cout << (dp[k] ? "First" : "Second");
}
Problem L - Deque#
又是賽局的題目，因為兩邊都可以拿東西，所以變成區間 dp。可以看出兩邊都是想讓自己分數越高越好，假設 \(f(l, r)\) 是 \([l, r]\) 區間中先手減後手的分數最大值（不一定是 \(X-Y\) 或 \(Y-X\)），轉移時 \(X, Y\) 會互換，所以變成要找最小值，也就是加負號，得到：
$$ f(l, r) = \max \{ a_l - f(l+1, r), a_r - f(l, r-1) \} $$
前者表示拿 \(l\)，後者表示拿 \(r\)，注意 \(l\) 跟 \(r\) 的計算方向是相反的，答案是整個區間，也就是 \(f(1, n)\)。
AC code
int n, a[MAXN], dp[MAXN][MAXN];
signed main() {
hyper;
cin >> n;
rep1(i,1,n) {
cin >> a[i];
dp[i][i] = a[i];
}
for(int l=n; l>=1; --l) {
rep1(r,l+1,n) {
dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1]);
}
}
cout << dp[1][n];
}
Problem M - Candies#
設 \(f(i, j)\) 是考慮到第 \(i\) 個小孩，用掉 \(j\) 個糖果時的方法數，則：
$$ f(i, j) = \sum_{k = j - a_{i}}^{j} f(i-1, k) $$
但這樣時間會炸，很容易發現可以用前綴和處理連續區間和，就可以把時間降到 \(O(nk)\)。然後可以用滾動 dp 進一步變成一維空間，好耶。
AC code
int n, k, a[MAXN], dp[MAXK], ps[MAXK];
signed main() {
hyper;
cin >> n >> k;
rep1(i,1,n) cin >> a[i];
rep1(j,0,k) {
dp[j] = (j <= a[1]);
ps[j+1] = ps[j] + dp[j];
}
rep1(i,2,n) {
rep1(j,0,k) dp[j] = (ps[j+1] - ps[max(0,j-a[i])]) % MOD;
rep1(j,0,k) ps[j+1] = ps[j] + dp[j];
}
cout << dp[k];
}
Problem N - Slimes#
典型區間 dp。定義 \(f_{i,j}\) 為合併第 \(i\) 到第 \(j\) 隻史萊姆的最小成本。則轉移式如下
$$ f_{i,j} = \min_{i \le k \le j} \left\{ f_{i,k} + f_{k+1,j} + \sum_{n=i}^{j} a_n \right\} $$
其中 \(\sum_{n=i}^{j} a_n\) 可以用前綴和 \(O(1)\) 處理掉，總複雜度 \(O(N^3)\)。
AC code
int n, a[MAXN], dp[MAXN][MAXN], ps[MAXN];
signed main() {
hyper;
cin >> n;
rep1(i,1,n) {
cin >> a[i];
dp[i][i] = 0;
ps[i] = ps[i-1] + a[i];
}
rep1(len,2,n) rep1(i,1,n-len+1) {
int j = i + len - 1;
dp[i][j] = INF;
rep(k,i,j) dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+ps[j]-ps[i-1]);
}
cout << dp[1][n];
}
Problem O - Matching#
本質上是二分圖完美匹配數量，用狀壓 dp 可以做。考慮 \(f_{i, S}\) 是前 \(i\) 個男生跟女生子集合 \(S\) 的匹配數，如果 \(a_{i,j} = 1\)，代表我可以把 \(j\) 加入 \(S\) 轉移過去，轉移變成：
$$ f_{i+1, S} = \sum_{j \in S, a_{i,j} = 1} f_{i, S \setminus \{j\}} $$
答案是 \(f_{N, \{0, 1, \dots, N-1\}}\)，時間複雜度是 \(O(2^N \cdot N)\)。
AC code
int n, dp[22][1<<21];
bool a[21][21];
signed main() {
hyper;
cin >> n;
rep(i,0,n) rep(j,0,n) cin >> a[i][j];
dp[0][0] = 1;
rep(i,0,n) rep(t,0,1<<n) {
if(dp[i][t] == 0) continue;
rep(j,0,n) if(!(t&(1<<j)) && a[i][j]) {
dp[i+1][t|(1<<j)] = (dp[i+1][t|(1<<j)] + dp[i][t]) % MOD;
}
}
cout << dp[n][(1<<n)-1];
}
Problem P - Independent Set#
樹上 dp 題，把節點是黑或白的方法數分開討論，定義 \(f_{u, c}, c \in \{0, 1\}\) 表示節點顏色，是根為 \(u\) 的子樹在 \(u\) 顏色是 \(c\) 時的答案，轉移時就可以分顏色討論，在 dfs 時順便把小孩的答案乘上去，複雜度 \(O(N)\)。
AC code
int n, dp[MN][2];
vector<int> e[MN];
void dfs(int u, int p) {
dp[u][0] = dp[u][1] = 1;
if(u != 1 && e[u].size() == 1) return;
for(int v: e[u]) {
if(v == p) continue;
dfs(v, u);
dp[u][0] = (dp[u][0] * (dp[v][0] + dp[v][1])) % MOD;
dp[u][1] = (dp[u][1] * dp[v][0]) % MOD;
}
}
signed main() {
hyper;
cin >> n;
rep(i,0,n-1) {
int x, y;
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1, 0);
cout << (dp[1][0] + dp[1][1]) % MOD;
}
Problem Q - Flowers#
看起來是帶權重的 LIS，定義 \(f_i\) 是選擇的最後一朵是第 \(i\) 朵花的答案，因此只能從高度比目前小的轉移過來，轉移式是：
$$ f_i = \max_{t < i, h_t < h_i} f_t + a_i $$
而答案是 \(\sum f_i\)，但這樣複雜度會變 \(O(N^2)\) 不會過。我們把高度排序當作 index，就變成單點查詢、區間最大值的問題，簡單用個 BIT（或線段樹）加速就過了，時間複雜度變成 \(O(N \log N)\)，好耶。
AC code
struct Fenwick {
vector<int> v;
int sz;
Fenwick(int n) {
v.resize(n+1, 0);
sz = n;
}
int lowbit(int x) { return x&-x; }
void modify(int p, int x) {
for(int i=p; i<=sz; i+=lowbit(i)) v[i] = max(v[i], x);
}
int query(int p) {
int mx = -INF;
for(int i=p; i>0; i-=lowbit(i)) mx = max(mx, v[i]);
return mx;
}
};
Fenwick bit(MN);
signed main() {
hyper;
int n;
vi h(MN), a(MN);
cin >> n;
rep1(i,1,n) cin >> h[i];
rep1(i,1,n) cin >> a[i];
vi tmp(h), idx(MN);
sort(tmp.begin()+1, tmp.begin()+1+n);
rep1(i,1,n) idx[tmp[i]] = i;
int ans = -INF;
rep1(i,1,n) {
int t = max(bit.query(idx[h[i]]-1), 0) + a[i];
bit.modify(idx[h[i]], t);
ans = max(ans, t);
}
cout << ans << '\n';
}
Problem R - Walk#
這題完全在考矩陣乘法，設 \(f(u, v, t)\) 表示從 \(u\) 到 \(v\) 走 \(t\) 步的方法數，則 \(f(u, v, 2t) = \sum_{k \in V} f(u, k, t) \times f(k, v, t)\)，所以用矩陣快速冪算出 \(a^K\) 然後把所有 entries 相加就是答案ㄌ。時間複雜度是 \(O(N^3 \log K)\)。
AC code
mat operator*(const mat &a, const mat &b) {
int n = a.size();
mat c(n, vi(n, 0));
rep(i,0,n) rep(j,0,n) rep(k,0,n)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
return c;
}
mat operator^(mat a, int k) {
int n = a.size();
mat b(n, vi(n, 0));
rep(i,0,n) b[i][i] = 1;
while(k) {
if(k & 1) b = b * a;
a = a * a;
k >>= 1;
}
return b;
}
signed main() {
hyper;
int n, k;
cin >> n >> k;
mat a(n, vi(n));
rep(i,0,n) rep(j,0,n) cin >> a[i][j];
mat b = a ^ k;
int sum = 0;
rep(i,0,n) rep(j,0,n) sum = (sum + b[i][j]) % MOD;
cout << sum << '\n';
}
Problem S - Digit Sum#
數位 dp 是我之前沒有碰過的題型，所以看 OI Wiki 研究了一下。
要記錄三個東西，目前位數、總和（取模）、以及前面所有位數是否達到上限（lim）。lim 是一個布林值，舉例來說，\(k\) 是 \(54321\)，假設我考慮了前三位是 \(543\)，那此時 lim 是 true，表示第四位只能填 \(0 \sim 2\)；否則假設前三位是 \(522\) 沒有達到上限，那 lim 就是 false，第四位可以隨便填。
轉移的部分看 code 應該就很清楚了，數位 dp 轉移關係比較複雜，用記憶化搜索比較好寫。記得最後答案要減一因為會把 0 也算進去。
AC code
string k;
int d, n;
int dp[10005][105][2];
int sol(int pos, int sum, int lim) {
if(pos == n) return sum == 0;
int& ret = dp[pos][sum][lim];
if(~ret) return ret;
ret = 0;
int up = lim ? k[pos] - '0' : 9;
rep1(i,0,up) ret += sol(pos+1, (sum+i)%d, lim&&(i==up));
return ret %= MOD;
}
signed main() {
hyper;
rr(dp, -1);
cin >> k >> d;
n = k.size();
cout << (sol(0, 0, 1) - 1 + MOD) % MOD << '\n';
}
Problem T - Permutation#
這題我覺得有點 tricky，首先最直接想到的是目前處理到的位置跟最後一位數字，這兩個是要記錄的狀態。因此我們定義 \(f(i, j)\) 是長度 \(i\) 且最後一位為 \(j\) 的方法數（用 \(1 \sim i\) 的正整數排列）。關鍵在於我們可以從 \(i-1\) 轉移過來，因為我們可以調整數字，只要不影響大小順序。例如原先是 \((1, 3, 2)\) 而第四位想要是 \(2\) 的話，只要把前三位數都 \(+1\) 就可以了，也就是變成 \((1, 4, 3, 2)\)。考慮 \(>\) 或 \(<\) 能讓上一個數字是多少，我們可以得到轉移式：
$$ f(i, j) = \begin{cases} \sum_{k=1}^{j} f(i-1, k), \quad (<) \\ \sum_{k=j}^{i-1} f(i-1, k), \quad (>) \end{cases} $$
然後簡單用前綴和處理，記得取模。
AC code
signed main() {
hyper;
int n;
string s;
cin >> n >> s;
mat dp(n+1, vi(n+1, 0));
dp[1][1] = 1;
rep1(i,2,n) {
vi ps(i+1, 0);
rep1(j,1,i-1) ps[j] = (ps[j-1] + dp[i-1][j]) % MOD;
rep1(j,1,i) {
if(s[i-2] == '<') dp[i][j] = ps[j-1];
else dp[i][j] = (ps[i-1] - ps[j-1] + MOD) % MOD;
}
}
int ans = 0;
rep1(i,1,n) ans = (ans + dp[n][i]) % MOD;
cout << ans << '\n';
}