Bài 27: Quy hoạch động nâng cao trong C++ và Python: truy vết, QHĐ trên đoạn, QHĐ bitmask và QHĐ chữ số
Lời mở đầu
Ở bài 19 em đã học quy hoạch động theo 5 bước: định nghĩa trạng thái, tìm công thức truy hồi, xác định cơ sở, chọn thứ tự tính và lấy đáp án. Với khung đó em đã giải được đường đi trên lưới, cái túi, dãy con tăng dài nhất, đổi tiền. Nhưng đề thi thật thường hỏi thêm: “in ra đường đi đó”, “chọn những vật nào”. Và nhiều bài có trạng thái không phải là “tiền tố i” quen thuộc mà là một đoạn $[l, r]$, một tập con hay các chữ số của một số.
Bài này đi qua bốn kỹ thuật đó. Phần bitmask dùng lại các phép toán bit ở bài 20, phần chữ số viết bằng đệ quy có nhớ. Cuối bài có một bảng giúp em nhận dạng nhanh một bài QHĐ thuộc dạng nào, đây là kỹ năng quan trọng nhất khi ngồi trong phòng thi.
tight để đếm số trong đoạn $[A, B]$ tới $10^{18}$; các mẹo giảm bộ nhớ và bảng nhận dạng dạng QHĐ. Có khung chạy tay LCS và QHĐ trên đoạn, 3 mô phỏng tương tác và 8 bài tập kèm gợi ý.Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Truy vết: in ra chính lời giải
Bảng QHĐ chỉ lưu giá trị tốt nhất. Nhưng mỗi ô được tính ra từ một lựa chọn cụ thể (đi từ trên xuống hay từ trái sang, lấy vật hay không lấy…). Nếu biết mỗi ô được tính từ ô nào, ta đứng ở ô đáp án rồi đi ngược lại từng bước là dựng được lời giải. Có hai cách làm:
- Lưu nguồn: khi tính
dp[i][j], ghi luôn vào mảngtr[i][j]là ô nào (hay lựa chọn nào) cho ra giá trị đó. Truy vết chỉ việc đọc mảngtr. - Tính lại khi đi ngược: không cần mảng phụ. Đứng ở một ô, thử từng lựa chọn trong công thức xem lựa chọn nào cho đúng bằng giá trị đang có thì lùi theo lựa chọn đó.
Cách thứ hai tiết kiệm bộ nhớ và hay dùng hơn; ba ví dụ dưới đây đều làm theo cách này.
Ví dụ 1: đường đi có tổng lớn nhất trên lưới. Từ ô $(1, 1)$ đi tới ô $(n, m)$, mỗi bước sang phải (R) hoặc xuống dưới (D). Như bài 19: $dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + a[i][j]$. Muốn in đường đi, đứng ở $(n, m)$: nếu ô trên lớn hơn hoặc bằng ô trái thì ô hiện tại được tính từ ô trên, tức là bước cuối là D; ngược lại bước cuối là R. Lùi về ô đó và lặp lại tới khi về $(1, 1)$. Vì đi ngược nên các bước thu được theo thứ tự ngược, cuối cùng phải đảo lại.
| hàng \ cột | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 1 (1) | 4 (3) | 5 (1) | 7 (2) |
| 2 | 3 (2) | 3 (-1) | 10 (5) | 11 (1) |
| 3 | 7 (4) | 9 (2) | 11 (1) | 14 (3) |
Bảng 1. Mỗi ô ghi $dp[i][j]$ và (trong ngoặc) số trên lưới. Từ ô $(3, 4)$ = 14 đi ngược: ô trên 11 ≥ ô trái 11 → lên; ô trên 7 < ô trái 10 → sang trái; … Đường xanh lá là R R D R D, tổng 1 + 3 + 1 + 5 + 1 + 3 = 14.
Xem code C++ / Python: in đường đi có tổng lớn nhất trên lưới (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long a[1005][1005], dp[1005][1005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> a[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
if(i == 1 && j == 1) dp[i][j] = a[i][j];
else if(i == 1) dp[i][j] = dp[i][j - 1] + a[i][j];
else if(j == 1) dp[i][j] = dp[i - 1][j] + a[i][j];
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
}
// TRUY VẾT: đứng ở (n, m), hỏi "ô này được tính từ ô nào?" rồi lùi về ô đó
string path = "";
int i = n, j = m;
while(i > 1 || j > 1){
if(j == 1 || (i > 1 && dp[i - 1][j] >= dp[i][j - 1])){
path += 'D'; i--; // đến từ ô trên: bước cuối là đi xuống
} else {
path += 'R'; j--; // đến từ ô trái: bước cuối là sang phải
}
}
reverse(path.begin(), path.end()); // đi ngược nên phải đảo lại
cout << dp[n][m] << "\n" << path;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [[int(data[2 + i * m + j]) for j in range(m)] for i in range(n)]
dp = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if i == 0 and j == 0:
dp[i][j] = a[i][j]
elif i == 0:
dp[i][j] = dp[i][j - 1] + a[i][j]
elif j == 0:
dp[i][j] = dp[i - 1][j] + a[i][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j]
# TRUY VẾT: đứng ở ô cuối, lùi về ô đã cho ra giá trị của nó
path = []
i, j = n - 1, m - 1
while i > 0 or j > 0:
if j == 0 or (i > 0 and dp[i - 1][j] >= dp[i][j - 1]):
path.append('D'); i -= 1 # đến từ ô trên
else:
path.append('R'); j -= 1 # đến từ ô trái
print(dp[n - 1][m - 1])
print(''.join(reversed(path))) # đi ngược nên phải đảo lạiVí dụ 2: in các vật của bài cái túi. $dp[i][c]$ là giá trị lớn nhất khi chỉ dùng $i$ vật đầu với sức chứa $c$: $dp[i][c] = \max(dp[i-1][c],\ dp[i-1][c - w_i] + v_i)$. Đứng ở $(n, W)$ đi ngược: nếu $dp[i][c] = dp[i-1][c]$ thì có một cách tối ưu không cần vật $i$, ta bỏ qua nó; còn nếu $dp[i][c] \ne dp[i-1][c]$ thì chắc chắn vật $i$ đã được lấy, ghi nhận nó và giảm $c$ đi $w_i$.
| vật i \ sức chứa c | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 (chưa có vật) | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 (w=2, v=3) | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 (w=3, v=4) | 0 | 0 | 3 | 4 | 4 | 7 |
| 3 (w=4, v=5) | 0 | 0 | 3 | 4 | 5 | 7 |
| 4 (w=5, v=6) | 0 | 0 | 3 | 4 | 5 | 7 |
Bảng 2. Cái túi sức chứa 5 với 4 vật. Đi ngược từ ô $(4, 5)$ = 7: hàng 4, 3 giữ nguyên giá trị so với hàng trên (số in đậm, không lấy); ở hàng 2 giá trị 7 ≠ 3 nên lấy vật 2, c còn 2; ở hàng 1 giá trị 3 ≠ 0 nên lấy vật 1. Đáp án: vật 1 và 2, tổng giá trị 7.
Xem code C++ / Python: cái túi có in ra các vật được chọn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int w[105], v[105];
long long dp[105][10005];
int main(){
int n, W;
cin >> n >> W;
for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for(int i = 1; i <= n; i++)
for(int c = 0; c <= W; c++){
dp[i][c] = dp[i - 1][c]; // không lấy vật i
if(c >= w[i]) dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i]] + v[i]); // lấy vật i
}
// TRUY VẾT: dp[i][c] khác dp[i - 1][c] nghĩa là bắt buộc phải lấy vật i
vector<int> chosen;
int c = W;
for(int i = n; i >= 1; i--)
if(dp[i][c] != dp[i - 1][c]){
chosen.push_back(i);
c -= w[i];
}
reverse(chosen.begin(), chosen.end());
cout << dp[n][W] << "\n" << chosen.size() << "\n";
for(int x : chosen) cout << x << " ";
return 0;
}import sys
data = sys.stdin.read().split()
n, W = int(data[0]), int(data[1])
w = [0] * (n + 1); v = [0] * (n + 1)
for i in range(1, n + 1):
w[i], v[i] = int(data[2 * i]), int(data[2 * i + 1])
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
prev, cur, wi, vi = dp[i - 1], dp[i], w[i], v[i]
for c in range(W + 1):
cur[c] = prev[c] # không lấy vật i
if c >= wi and prev[c - wi] + vi > cur[c]:
cur[c] = prev[c - wi] + vi # lấy vật i
# TRUY VẾT: dp[i][c] khác dp[i - 1][c] nghĩa là bắt buộc phải lấy vật i
chosen, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i - 1][c]:
chosen.append(i)
c -= w[i]
chosen.reverse()
print(dp[n][W])
print(len(chosen))
print(*chosen)bool lay[i][c] (1 byte mỗi ô) để ghi lựa chọn, còn giá trị vẫn nén 1 chiều.Ví dụ 3: xâu con chung dài nhất (LCS). Cho hai xâu $s$ (dài $n$) và $t$ (dài $m$). Xâu con là xâu thu được khi xoá đi một số ký tự (giữ thứ tự các ký tự còn lại). Tìm xâu dài nhất là xâu con của cả hai. Gọi $dp[i][j]$ là độ dài LCS của $i$ ký tự đầu của $s$ và $j$ ký tự đầu của $t$. Xét hai ký tự cuối $s_i$ và $t_j$:
- Nếu $s_i = t_j$: ghép ký tự này vào sau LCS của phần còn lại, $dp[i][j] = dp[i-1][j-1] + 1$.
- Nếu $s_i \ne t_j$: một trong hai ký tự không được dùng, $dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1])$.
Truy vết đi ngược từ $(n, m)$: hai ký tự khớp thì ký tự đó thuộc LCS, đi chéo; không khớp thì đi về phía ô lớn hơn (trên hoặc trái). Em xem kỹ cả hai pha trong mô phỏng:
| s \ t | ∅ | B | D | C | A | B |
|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 |
| B | 0 | 1 | 1 | 2 | 2 | 3 |
| D | 0 | 1 | 2 | 2 | 2 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 |
Bảng 3. Bảng LCS của s = ABCBDA và t = BDCAB. Ô xanh lá là những chỗ hai ký tự khớp và được lấy (đọc từ trên xuống: B, C, B), số in đậm không tô màu là những bước chỉ đi lên hoặc sang trái. LCS = BCB, độ dài 3.
Xem code C++ / Python: xâu con chung dài nhất có truy vết (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main(){
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
string res = "";
int i = n, j = m;
while(i > 0 && j > 0){
if(s[i - 1] == t[j - 1]){
res += s[i - 1]; i--; j--;
}
else if(dp[i - 1][j] >= dp[i][j - 1]) i--;
else j--;
}
reverse(res.begin(), res.end());
cout << dp[n][m] << "\n" << res;
return 0;
}import sys
s, t = sys.stdin.read().split()[:2]
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
res = []
i, j = n, m
while i > 0 and j > 0: # truy vết từ góc dưới phải
if s[i - 1] == t[j - 1]:
res.append(s[i - 1]); i -= 1; j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
print(dp[n][m])
print(''.join(reversed(res)))// 1. Tính xong toàn bộ bảng dp (giữ đủ các chiều)
// 2. Đứng ở trạng thái đáp án
while(chưa về trạng thái cơ sở){
for(mỗi lựa chọn có thể dẫn tới trạng thái hiện tại)
if(dp[hiện tại] == dp[trạng thái trước] + chi phí lựa chọn){
ghi nhận lựa chọn; hiện tại = trạng thái trước; break;
}
}
// 3. Đảo ngược danh sách lựa chọn đã ghiPhần 2QHĐ trên đoạn
Nhiều bài có cấu trúc: đáp án của cả đoạn $[l, r]$ được ghép từ đáp án của các đoạn con bên trong. Khi đó trạng thái là $dp[l][r]$, và công thức thường có một trong hai dáng:
- Bóc hai đầu: $dp[l][r]$ tính từ $dp[l+1][r]$, $dp[l][r-1]$, $dp[l+1][r-1]$ (xâu đối xứng, trò chơi lấy hai đầu dãy). Độ phức tạp $O(n^2)$.
- Chọn điểm chia $k$: $dp[l][r] = \min_{l \le k < r} \big(dp[l][k] + dp[k+1][r]\big) + \text{chi phí ghép}$ (ghép đá, nhân dãy ma trận, cắt que). Độ phức tạp $O(n^3)$.
Ví dụ: chèn ít ký tự nhất để thành xâu đối xứng. Cho xâu $s$, được chèn ký tự vào vị trí bất kỳ. Hỏi phải chèn ít nhất bao nhiêu ký tự để $s$ đọc xuôi ngược như nhau? Gọi $dp[l][r]$ là đáp án cho đoạn $s[l..r]$. Nhìn hai đầu:
- $s_l = s_r$: hai đầu tự làm cặp với nhau, $dp[l][r] = dp[l+1][r-1]$.
- $s_l \ne s_r$: phải chèn một ký tự để ghép cặp với một đầu. Chèn bản sao của $s_l$ vào cuối thì còn lại đoạn $[l+1, r]$; chèn bản sao của $s_r$ vào đầu thì còn lại $[l, r-1]$. Vậy $dp[l][r] = \min(dp[l+1][r],\ dp[l][r-1]) + 1$.
Cơ sở: $dp[i][i] = 0$ và đoạn rỗng bằng 0. Câu hỏi quan trọng là thứ tự tính. Nếu duyệt $l$ từ 0 lên như thói quen thì lúc tính $dp[0][4]$, ô $dp[1][4]$ chưa có! Mọi ô cần đến đều là đoạn ngắn hơn, nên ta duyệt theo độ dài đoạn tăng dần: điền đường chéo chính, rồi đường chéo kế tiếp, … tới ô góc trên phải $dp[0][n-1]$.
Xem code C++ / Python: chèn ít ký tự nhất để thành xâu đối xứng (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int dp[5005][5005];
int main(){
string s;
cin >> s;
int n = s.size();
for(int len = 2; len <= n; len++)
for(int l = 0; l + len - 1 < n; l++){
int r = l + len - 1;
if(s[l] == s[r])
dp[l][r] = dp[l + 1][r - 1];
else
dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1;
}
cout << dp[0][n - 1];
return 0;
}s = input().strip()
n = len(s)
dp = [[0] * n for _ in range(n)] # dp[i][i] = 0: một ký tự đã đối xứng
for length in range(2, n + 1): # duyệt theo ĐỘ DÀI đoạn tăng dần
for l in range(n - length + 1):
r = l + length - 1
if s[l] == s[r]:
dp[l][r] = dp[l + 1][r - 1] # hai đầu tự ghép cặp
else:
dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1
print(dp[0][n - 1])Dạng chọn điểm chia: ghép đá. Có $n$ đống đá xếp thành hàng, đống thứ $i$ nặng $a_i$. Mỗi lần được gộp hai đống kề nhau thành một, chi phí bằng tổng khối lượng hai đống. Gộp tới khi còn một đống, hỏi tổng chi phí nhỏ nhất. Mấu chốt: lần gộp cuối cùng của đoạn $[l, r]$ luôn ghép một khối $[l, k]$ với một khối $[k+1, r]$, và lần gộp đó tốn đúng $a_l + \cdots + a_r$ (tính nhanh bằng mảng cộng dồn) bất kể $k$ là bao nhiêu. Vậy:
$dp[l][r] = \min\limits_{l \le k < r} \big(dp[l][k] + dp[k+1][r]\big) + (P_r - P_{l-1}), \qquad dp[i][i] = 0.$
| l \ r | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 7 | 15 | 28 |
| 2 | 0 | 6 | 17 | |
| 3 | 0 | 7 | ||
| 4 | 0 |
Bảng 4. Ghép 4 đống 3, 4, 2, 5. Ví dụ $dp[1][3] = \min(0 + dp[2][3],\ dp[1][2] + 0) + 9 = \min(6, 7) + 9 = 15$. Đáp án $dp[1][4] = 28$: gộp (3, 4) tốn 7, gộp (2, 5) tốn 7, gộp hai khối cuối tốn 14.
len từ 2 tới $n$, vòng trong là l (như code trên).2. Vòng ngoài
l chạy giảm từ $n-1$ về 0, vòng trong r chạy tăng từ l + 1: khi tính $(l, r)$ thì hàng $l+1$ và các ô bên trái của hàng $l$ đã xong.3. Đệ quy có nhớ
solve(l, r): không phải nghĩ thứ tự, nhưng chậm hơn và dễ tràn ngăn xếp khi $n$ lớn.Sai thứ tự là lỗi số một của QHĐ trên đoạn: chương trình vẫn chạy, chỉ là đọc phải những ô chưa tính (đang bằng 0).
Phần 3QHĐ bitmask: trạng thái là một tập con
Khi đề có $n$ nhỏ (thường $n \le 20$) và lời giải phụ thuộc vào việc những phần tử nào đã được dùng chứ không chỉ là bao nhiêu phần tử, ta mã hoá tập đã dùng thành một số nguyên mask (bit $j$ bằng 1 nghĩa là phần tử $j$ đã dùng), đúng như cách duyệt tập con ở bài 20. Có $2^n$ tập con, với $n = 20$ là khoảng $10^6$ trạng thái, vừa đủ để làm QHĐ. Các thao tác cần nhớ: kiểm tra mask >> j & 1, thêm phần tử mask | (1 << j), đếm số bit __builtin_popcount(mask).
Ví dụ 1: phân công. Có $n$ người và $n$ việc, người $i$ làm việc $j$ tốn $c_{ij}$. Mỗi người làm đúng một việc, mỗi việc do đúng một người làm. Tìm tổng chi phí nhỏ nhất. Thử mọi hoán vị tốn $n!$ (với $n = 15$ là $1{,}3 \cdot 10^{12}$). Nhận xét: nếu giao việc lần lượt cho người $0, 1, 2, \ldots$ thì khi đã giao xong tập việc mask, người tiếp theo chắc chắn là người thứ popcount(mask). Chi phí về sau chỉ phụ thuộc mask, không phụ thuộc ai làm việc nào trong mask. Vì vậy:
$dp[\text{mask} \cup \{j\}] = \min\big(dp[\text{mask} \cup \{j\}],\ dp[\text{mask}] + c[\text{popcount(mask)}][j]\big), \quad j \notin \text{mask}.$
Có $2^n$ trạng thái, mỗi trạng thái thử $n$ việc: $O(2^n \cdot n)$, với $n = 20$ là khoảng $2 \cdot 10^7$ phép tính. Mọi tập con của mask đều nhỏ hơn mask nên chỉ cần duyệt mask từ 0 lên.
Xem code C++ / Python: phân công $n$ người $n$ việc bằng QHĐ bitmask (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, c[20][20];
long long dp[1 << 20];
int main(){
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) cin >> c[i][j];
fill(dp, dp + (1 << n), LLONG_MAX);
dp[0] = 0; // chưa giao việc nào
for(int mask = 0; mask < (1 << n); mask++){
if(dp[mask] == LLONG_MAX) continue;
int i = __builtin_popcount(mask); // người tiếp theo cần giao việc
if(i == n) continue;
for(int j = 0; j < n; j++)
if(!(mask >> j & 1)){ // việc j còn trống
int nm = mask | (1 << j);
dp[nm] = min(dp[nm], dp[mask] + c[i][j]);
}
}
cout << dp[(1 << n) - 1];
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
c = [[int(data[1 + i * n + j]) for j in range(n)] for i in range(n)]
INF = float('inf')
dp = [INF] * (1 << n)
dp[0] = 0 # chưa giao việc nào
for mask in range(1 << n):
if dp[mask] == INF:
continue
i = bin(mask).count('1') # người tiếp theo cần giao việc
if i == n:
continue
for j in range(n):
if not mask >> j & 1: # việc j còn trống
nm = mask | 1 << j
if dp[mask] + c[i][j] < dp[nm]:
dp[nm] = dp[mask] + c[i][j]
print(dp[(1 << n) - 1])Ví dụ 2: người du lịch (TSP). Có $n$ thành phố, $d_{ij}$ là quãng đường từ $i$ tới $j$. Xuất phát từ thành phố 0, đi qua mỗi thành phố đúng một lần rồi quay về 0. Tìm tổng quãng đường ngắn nhất. Lần này chỉ biết tập đã thăm là chưa đủ: bước tiếp theo tốn bao nhiêu còn tuỳ ta đang đứng ở đâu. Trạng thái cần hai thành phần:
$dp[\text{mask}][v]$ = quãng đường ngắn nhất xuất phát từ 0, đã thăm đúng tập $\text{mask}$ và hiện đang ở $v \in \text{mask}$.
Cơ sở $dp[\{0\}][0] = 0$. Từ $(\text{mask}, v)$ đi tiếp tới $u \notin \text{mask}$: cập nhật $dp[\text{mask} \cup \{u\}][u]$ bằng $dp[\text{mask}][v] + d_{vu}$. Đáp án là $\min_v \big(dp[\text{tất cả}][v] + d_{v0}\big)$. Có $2^n \cdot n$ trạng thái, mỗi trạng thái thử $n$ bước đi: $O(2^n n^2)$. Với $n = 15$ là khoảng $7 \cdot 10^6$, rất nhanh.
Hình 1. Bốn thành phố. Chu trình xanh lá 0 → 1 → 3 → 2 → 0 dài 80 là ngắn nhất. Ví dụ $dp[\{0,1,3\}][3] = 10 + 25 = 35$, rồi $dp[\{0,1,2,3\}][2] = 35 + 30 = 65$, cộng $d_{20} = 15$ được 80.
Xem code C++ / Python: người du lịch (TSP) bằng QHĐ bitmask $O(2^n n^2)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int n;
long long d[16][16], dp[1 << 15][15];
int main(){
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) cin >> d[i][j];
for(int mask = 0; mask < (1 << n); mask++)
for(int v = 0; v < n; v++) dp[mask][v] = INF;
dp[1][0] = 0; // mới ở thành phố 0, đã thăm {0}
for(int mask = 1; mask < (1 << n); mask++)
for(int v = 0; v < n; v++){
if(dp[mask][v] == INF) continue;
for(int u = 0; u < n; u++){
if(mask >> u & 1) continue; // u đã thăm rồi
int nm = mask | (1 << u);
dp[nm][u] = min(dp[nm][u], dp[mask][v] + d[v][u]);
}
}
long long ans = INF;
int full = (1 << n) - 1;
for(int v = 0; v < n; v++) ans = min(ans, dp[full][v] + d[v][0]); // quay về 0
cout << ans;
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
d = [[int(data[1 + i * n + j]) for j in range(n)] for i in range(n)]
INF = float('inf')
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # mới ở thành phố 0, đã thăm {0}
for mask in range(1, 1 << n):
row = dp[mask]
for v in range(n):
cur = row[v]
if cur == INF:
continue
dv = d[v]
for u in range(n):
if mask >> u & 1: # u đã thăm rồi
continue
nm = mask | 1 << u
if cur + dv[u] < dp[nm][u]:
dp[nm][u] = cur + dv[u]
full = (1 << n) - 1
print(min(dp[full][v] + d[v][0] for v in range(n))) # quay về 0long long dp[1 << 20][20] tốn $2^{20} \cdot 20 \cdot 8 \approx 168$ MB, thường vượt giới hạn. Hãy dùng int nếu đáp án đủ nhỏ, hoặc giảm chiều. Dấu hiệu nhận dạng QHĐ bitmask: $n \le 15 \ldots 20$ (rất nhỏ một cách đáng ngờ) và bài hỏi về thứ tự hoặc cách ghép cặp các phần tử. Python chậm hơn C++ nhiều lần, nên khi luyện bằng Python em nên thử với $n \le 13$.Phần 4QHĐ chữ số: đếm số trong đoạn [A, B]
Bài toán: đếm số nguyên trong đoạn $[A, B]$ ($0 \le A \le B \le 10^{18}$) có tổng các chữ số chia hết cho $K$ ($K \le 100$). Duyệt từng số là không thể. Ý tưởng: thay vì duyệt các số, ta xây số từng chữ số một, từ trái sang phải, và đếm bằng QHĐ.
Bước 1: đưa về đếm trên $[0, X]$. Gọi $\text{cnt}(X)$ là số lượng số trong $[0, X]$ thoả mãn. Đáp án là $\text{cnt}(B) - \text{cnt}(A - 1)$, giống hệt cách lấy tổng đoạn bằng mảng cộng dồn.
Bước 2: trạng thái. Viết $X$ thành xâu $n$ chữ số. Mọi số $y \le X$ được coi là có đúng $n$ chữ số (thêm số 0 ở đầu, tổng chữ số không đổi). Ta điền các chữ số của $y$ từ vị trí 0 tới $n-1$. Cần nhớ:
pos: đang điền vị trí thứ mấy;sum: tổng các chữ số đã điền, lấy mod $K$ (chỉ cần biết số dư);tight: các chữ số đã điền có trùng hệt tiền tố của $X$ không. Nếu có thì chữ số tiếp theo chỉ được chọn từ 0 tới $X[\text{pos}]$ (vượt là $y > X$). Chỉ cần một lần chọn chữ số nhỏ hơn, $y$ đã chắc chắn nhỏ hơn $X$ và các vị trí sau được chọn tự do 0…9.
Bước 3: công thức. $f(\text{pos}, \text{sum}, \text{tight}) = \sum_{d=0}^{\text{lim}} f\big(\text{pos}+1,\ (\text{sum}+d) \bmod K,\ \text{tight} \wedge d = \text{lim}\big)$, với $\text{lim} = X[\text{pos}]$ nếu tight, ngược lại là 9. Khi $\text{pos} = n$: trả về 1 nếu $\text{sum} = 0$. Số trạng thái chỉ $19 \cdot K \cdot 2$, mỗi trạng thái thử 10 chữ số: khoảng $4 \cdot 10^4$ phép tính cho $X$ tới $10^{18}$!
Vì sao chỉ ghi nhớ khi tight = false? Có đúng một nhánh tight duy nhất (bám theo $X$), nên trạng thái tight chỉ được gọi một lần ở mỗi vị trí, ghi nhớ cũng không lợi gì. Còn các trạng thái tự do được gọi lại rất nhiều lần. Mô phỏng dưới đây đi dọc nhánh tight và cho em thấy ở mỗi vị trí, các nhánh rẽ sang chữ số nhỏ hơn được đếm gọn bằng bảng nhớ:
Xem code C++ / Python: đếm số trong $[A, B]$ có tổng chữ số chia hết cho $K$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
string X;
int K;
long long memo[20][105];
bool seen[20][105];
// số cách điền các chữ số từ vị trí pos trở đi, biết tổng các chữ số đã điền mod K là sum
long long f(int pos, int sum, bool tight){
if(pos == (int)X.size()) return sum == 0 ? 1 : 0;
if(!tight && seen[pos][sum]) return memo[pos][sum];
int lim = tight ? X[pos] - '0' : 9; // còn bám sát X thì không được vượt chữ số của X
long long res = 0;
for(int d = 0; d <= lim; d++)
res += f(pos + 1, (sum + d) % K, tight && d == lim);
if(!tight){ seen[pos][sum] = true; memo[pos][sum] = res; }
return res;
}
long long countUpTo(long long x){ // đếm số trong [0, x]
if(x < 0) return 0;
X = to_string(x);
memset(seen, 0, sizeof(seen)); // pos tính từ trái nên mỗi X có bảng nhớ riêng
return f(0, 0, true);
}
int main(){
long long A, B;
cin >> A >> B >> K;
cout << countUpTo(B) - countUpTo(A - 1);
return 0;
}import sys
from functools import lru_cache
def count_up_to(x, K): # đếm số trong [0, x]
if x < 0:
return 0
X = str(x)
@lru_cache(maxsize=None)
def f(pos, s, tight):
if pos == len(X):
return 1 if s == 0 else 0
lim = int(X[pos]) if tight else 9 # còn bám sát X thì không vượt chữ số của X
return sum(f(pos + 1, (s + d) % K, tight and d == lim) for d in range(lim + 1))
return f(0, 0, True)
A, B, K = map(int, sys.stdin.read().split())
print(count_up_to(B, K) - count_up_to(A - 1, K))long long f(int pos, /* thông tin cần nhớ */, bool tight, bool started){
if(pos == n) return (điều kiện cuối thoả) ? 1 : 0;
if(!tight && started && đã nhớ) return memo[...];
int lim = tight ? X[pos] - '0' : 9;
long long res = 0;
for(int d = 0; d <= lim; d++)
res += f(pos + 1, /* cập nhật thông tin */, tight && d == lim, started || d != 0);
ghi nhớ nếu !tight && started;
return res;
}started (đã gặp chữ số khác 0 chưa) chỉ cần khi số 0 ở đầu làm thay đổi điều kiện, ví dụ “hai chữ số kề nhau khác nhau” (bài tập 7): với số 7, các số 0 thêm vào đầu “007” không được coi là hai chữ số 0 kề nhau. Với tổng chữ số thì số 0 ở đầu vô hại nên bỏ cờ này.Phần 5Mẹo: giảm bộ nhớ, thứ tự tính, nhận dạng
Giảm chiều bộ nhớ. Nếu hàng $i$ chỉ dùng hàng $i-1$ thì chỉ cần giữ hai hàng (mảng lăn). LCS hai xâu dài $10^4$ cần $10^8$ ô nếu giữ cả bảng, nhưng chỉ cần $2 \cdot 10^4$ ô với hai hàng. Cái túi 0/1 còn nén được về một hàng nếu duyệt $c$ giảm dần, để $dp[c - w]$ vẫn là giá trị của hàng cũ. Cái giá phải trả: mất khả năng truy vết.
vector<int> prv(m + 1, 0), cur(m + 1, 0);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
cur[j] = (s[i - 1] == t[j - 1]) ? prv[j - 1] + 1 : max(prv[j], cur[j - 1]);
swap(prv, cur);
}
// đáp án: prv[m]prv[j], ô “trái” là cur[j - 1], ô “chéo” là prv[j - 1].Chọn thứ tự tính. Quy tắc duy nhất: ô nào được dùng thì phải tính trước. Vẽ mũi tên từ mỗi ô tới các ô nó cần, rồi chọn thứ tự vòng lặp đi ngược chiều mũi tên. Lưới và LCS cần ô trên, ô trái: duyệt hàng tăng, cột tăng. QHĐ trên đoạn cần đoạn ngắn hơn: duyệt theo độ dài. Bitmask cần tập con: duyệt mask tăng dần. Khi khó xác định, viết đệ quy có nhớ là an toàn nhất (QHĐ chữ số hầu như luôn viết kiểu này).
| Dạng | Trạng thái | Dấu hiệu trong đề | Độ phức tạp | Ví dụ |
|---|---|---|---|---|
| Tiền tố (bài 19) | $dp[i]$, $dp[i][c]$ | dãy, xét lần lượt từng phần tử; giới hạn $n \le 10^5$ | $O(n)$ … $O(nW)$ | cái túi, LIS, đổi tiền |
| Hai xâu / hai dãy | $dp[i][j]$ | hai dãy, so khớp, xoá/chèn/sửa ký tự; $n, m \le 5000$ | $O(nm)$ | LCS, khoảng cách sửa xâu |
| Trên đoạn | $dp[l][r]$ | gộp phần tử kề nhau, lấy ở hai đầu, đối xứng, đặt ngoặc; $n \le 500$ | $O(n^2)$, $O(n^3)$ | ghép đá, cắt que, xâu đối xứng |
| Bitmask | $dp[\text{mask}]$, $dp[\text{mask}][v]$ | $n \le 20$, thứ tự / ghép cặp / phân công | $O(2^n n)$, $O(2^n n^2)$ | TSP, phân công |
| Chữ số | $f(\text{pos}, \ldots, \text{tight})$ | đếm số trong $[A, B]$ với $B$ tới $10^{18}$, điều kiện trên chữ số | $O(\text{số chữ số} \cdot S \cdot 10)$ | tổng chữ số, số may mắn |
Bảng 5. Nhận dạng nhanh các dạng QHĐ. Giới hạn của $n$ trong đề thường là gợi ý mạnh nhất: $n \le 20$ gần như chắc chắn là bitmask, $n \le 500$ hay là QHĐ trên đoạn $O(n^3)$.
- Cái Túi 2 (BTKCATU2) (Trung bình)
- Phi Tiêu (PHITIEU) (Trung bình)
- Món Ăn (DPRCMA) (Trung bình)
- Biểu Thức Bằng K (EXPR) (Khá)
- Số May Mắn (Khá)
- Tổng Các Chữ Số (Khó)
- Parallel Courses II (LeetCode 1494) (Khó)
- Minimum Incompatibility (LeetCode 1681) (Khó)
Bài tậpLuyện quy hoạch động nâng cao
Cho lưới $n \times m$ ($1 \le n, m \le 500$) chứa số nguyên $|a_{ij}| \le 10^9$. Robot đi từ ô trái trên tới ô phải dưới, mỗi bước sang phải (R) hoặc xuống dưới (D). In ra tổng lớn nhất của các ô robot đi qua, và dòng thứ hai là đường đi gồm $n + m - 2$ ký tự. Nếu có nhiều đường cùng tổng lớn nhất, in đường có xâu nhỏ nhất theo thứ tự từ điển (D đứng trước R).
3 3
1 2 3
4 5 6
1 1 925
DRRD📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long a[505][505], g[505][505];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) cin >> a[i][j];
for(int i = n; i >= 1; i--) // g[i][j]: tổng lớn nhất từ (i, j) tới đích
for(int j = m; j >= 1; j--){
if(i == n && j == m) g[i][j] = a[i][j];
else if(i == n) g[i][j] = a[i][j] + g[i][j + 1];
else if(j == m) g[i][j] = a[i][j] + g[i + 1][j];
else g[i][j] = a[i][j] + max(g[i + 1][j], g[i][j + 1]);
}
string path = "";
int i = 1, j = 1;
while(i < n || j < m){ // đi xuôi, ưu tiên D khi hoà
if(j == m || (i < n && g[i + 1][j] >= g[i][j + 1])){ path += 'D'; i++; }
else { path += 'R'; j++; }
}
cout << g[1][1] << "\n" << path;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [[int(data[2 + i * m + j]) for j in range(m)] for i in range(n)]
g = [[0] * m for _ in range(n)] # g[i][j]: tổng lớn nhất từ (i, j) tới đích
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
if i == n - 1 and j == m - 1:
g[i][j] = a[i][j]
elif i == n - 1:
g[i][j] = a[i][j] + g[i][j + 1]
elif j == m - 1:
g[i][j] = a[i][j] + g[i + 1][j]
else:
g[i][j] = a[i][j] + max(g[i + 1][j], g[i][j + 1])
path = []
i = j = 0
while i < n - 1 or j < m - 1: # đi xuôi, ưu tiên D khi hoà
if j == m - 1 or (i < n - 1 and g[i + 1][j] >= g[i][j + 1]):
path.append('D'); i += 1
else:
path.append('R'); j += 1
print(g[0][0])
print(''.join(path))Cho hai xâu $s, t$ gồm chữ cái thường, độ dài không quá 1000. In ra độ dài xâu con chung dài nhất, và dòng thứ hai là một xâu con chung dài nhất. Nếu có nhiều xâu như vậy, in xâu nhỏ nhất theo thứ tự từ điển. (Nếu độ dài là 0 thì dòng thứ hai để trống.)
abcbda
bdcab3
bca📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
nxt tính trước). Nếu $suf[p+1][q+1] = suf[i][j] - 1$ thì $c$ mở đầu được một LCS: lấy $c$, nhảy tới $(p+1, q+1)$. Lấy lần xuất hiện sớm nhất là tốt nhất vì phần còn lại dài nhất có thể. Mỗi ký tự của đáp án thử tối đa 26 chữ cái.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int suf[1005][1005], ns[1005][26], nt[1005][26];
int main(){
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
for(int i = n - 1; i >= 0; i--)
for(int j = m - 1; j >= 0; j--)
suf[i][j] = (s[i] == t[j]) ? suf[i + 1][j + 1] + 1 : max(suf[i + 1][j], suf[i][j + 1]);
for(int c = 0; c < 26; c++){ ns[n][c] = n; nt[m][c] = m; }
for(int i = n - 1; i >= 0; i--){ // ns[i][c]: vị trí đầu tiên >= i có chữ c
for(int c = 0; c < 26; c++) ns[i][c] = ns[i + 1][c];
ns[i][s[i] - 'a'] = i;
}
for(int j = m - 1; j >= 0; j--){
for(int c = 0; c < 26; c++) nt[j][c] = nt[j + 1][c];
nt[j][t[j] - 'a'] = j;
}
string res = "";
int i = 0, j = 0;
while(suf[i][j] > 0){
for(int c = 0; c < 26; c++){
int p = ns[i][c], q = nt[j][c];
if(p < n && q < m && suf[p + 1][q + 1] == suf[i][j] - 1){
res += char('a' + c);
i = p + 1; j = q + 1;
break;
}
}
}
cout << suf[0][0] << "\n" << res;
return 0;
}import sys
s, t = sys.stdin.read().split()[:2]
n, m = len(s), len(t)
suf = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
row, nxt, si = suf[i], suf[i + 1], s[i]
for j in range(m - 1, -1, -1):
if si == t[j]:
row[j] = nxt[j + 1] + 1
else:
row[j] = nxt[j] if nxt[j] > row[j + 1] else row[j + 1]
def build_next(x): # nx[i][c]: vị trí đầu tiên >= i có chữ c
L = len(x)
nx = [[L] * 26 for _ in range(L + 1)]
for i in range(L - 1, -1, -1):
nx[i] = nx[i + 1][:]
nx[i][ord(x[i]) - 97] = i
return nx
ns, nt = build_next(s), build_next(t)
res = []
i = j = 0
while suf[i][j] > 0:
for c in range(26):
p, q = ns[i][c], nt[j][c]
if p < n and q < m and suf[p + 1][q + 1] == suf[i][j] - 1:
res.append(chr(97 + c))
i, j = p + 1, q + 1
break
print(suf[0][0])
print(''.join(res))Cho xâu $s$ gồm chữ cái thường, độ dài $n \le 1000$. Được chèn thêm ký tự vào vị trí bất kỳ. Hỏi cần chèn ít nhất bao nhiêu ký tự để $s$ trở thành xâu đối xứng?
mbadm2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int n = s.size();
vector<int> nxt(n, 0), cur(n, 0); // nxt = hàng l + 1, cur = hàng l
for(int l = n - 1; l >= 0; l--){
cur[l] = 0;
for(int r = l + 1; r < n; r++){
if(s[l] == s[r]) cur[r] = (r - l >= 2) ? nxt[r - 1] : 0;
else cur[r] = min(nxt[r], cur[r - 1]) + 1;
}
swap(nxt, cur);
}
cout << nxt[n - 1];
return 0;
}s = input().strip()
n = len(s)
nxt = [0] * n # hàng l + 1
for l in range(n - 1, -1, -1):
cur = [0] * n # hàng l
sl = s[l]
for r in range(l + 1, n):
if sl == s[r]:
cur[r] = nxt[r - 1] if r - l >= 2 else 0
else:
a, b = nxt[r], cur[r - 1]
cur[r] = (a if a < b else b) + 1
nxt = cur
print(nxt[n - 1])Có $n$ đống đá xếp thành hàng ($1 \le n \le 200$), đống thứ $i$ nặng $a_i$ ($1 \le a_i \le 10^6$). Mỗi lần được gộp hai đống kề nhau thành một đống, chi phí bằng tổng khối lượng của hai đống. Tìm tổng chi phí nhỏ nhất để gộp tất cả thành một đống.
4
3 4 2 528📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long P[205], dp[205][205];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){ long long x; cin >> x; P[i] = P[i - 1] + x; }
for(int len = 2; len <= n; len++)
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for(int k = l; k < r; k++) // lần gộp cuối: [l, k] với [k + 1, r]
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += P[r] - P[l - 1];
}
cout << dp[1][n];
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
P = [0]
for x in data[1:n + 1]:
P.append(P[-1] + int(x))
dp = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1):
for l in range(1, n - length + 2):
r = l + length - 1
row = dp[l]
best = min(row[k] + dp[k + 1][r] for k in range(l, r)) # lần gộp cuối
row[r] = best + P[r] - P[l - 1]
print(dp[1][n])Một que gỗ dài $L$ ($L \le 10^9$) cần cắt tại $m$ vị trí cho trước ($1 \le m \le 200$, các vị trí khác nhau, nằm trong khoảng $(0, L)$). Mỗi lần chỉ cắt một khúc tại một điểm, chi phí bằng độ dài khúc đang cắt. Thứ tự cắt tuỳ ý. Tìm tổng chi phí nhỏ nhất.
Dòng đầu là $L$ và $m$, dòng sau là $m$ vị trí cắt (không nhất thiết tăng dần).
10 3
2 4 720📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long p[205], dp[205][205];
int main(){
long long L; int m;
cin >> L >> m;
for(int i = 1; i <= m; i++) cin >> p[i];
p[0] = 0; p[m + 1] = L;
sort(p, p + m + 2);
for(int len = 2; len <= m + 1; len++) // len = j - i
for(int i = 0; i + len <= m + 1; i++){
int j = i + len;
dp[i][j] = LLONG_MAX;
for(int k = i + 1; k < j; k++) // cắt đầu tiên tại p[k]
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
dp[i][j] += p[j] - p[i];
}
cout << dp[0][m + 1];
return 0;
}import sys
data = sys.stdin.read().split()
L, m = int(data[0]), int(data[1])
p = sorted([0, L] + [int(x) for x in data[2:2 + m]])
N = m + 2
dp = [[0] * N for _ in range(N)]
for length in range(2, N): # length = j - i
for i in range(N - length):
j = i + length
row = dp[i]
row[j] = min(row[k] + dp[k][j] for k in range(i + 1, j)) + p[j] - p[i] # cắt đầu tiên tại p[k]
print(dp[0][N - 1])Có $n$ bạn ($1 \le n \le 16$) và $n$ nhiệm vụ. Bảng $n \times n$ gồm các số 0/1: số ở hàng $i$, cột $j$ bằng 1 nếu bạn $i$ làm được nhiệm vụ $j$. Đếm số cách giao cho mỗi bạn đúng một nhiệm vụ mình làm được, sao cho mỗi nhiệm vụ có đúng một bạn nhận.
3
110
111
0113📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long dp[1 << 16];
int main(){
int n;
cin >> n;
vector<string> g(n);
for(auto &row : g) cin >> row;
dp[0] = 1;
for(int mask = 0; mask < (1 << n); mask++){
if(!dp[mask]) continue;
int i = __builtin_popcount(mask); // bạn tiếp theo
if(i == n) continue;
for(int j = 0; j < n; j++)
if(g[i][j] == '1' && !(mask >> j & 1))
dp[mask | (1 << j)] += dp[mask];
}
cout << dp[(1 << n) - 1];
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
g = data[1:1 + n]
can = [[j for j in range(n) if g[i][j] == '1'] for i in range(n)]
dp = [0] * (1 << n)
dp[0] = 1
for mask in range(1 << n):
v = dp[mask]
if not v:
continue
i = bin(mask).count('1') # bạn tiếp theo
if i == n:
continue
for j in can[i]:
if not mask >> j & 1:
dp[mask | 1 << j] += v
print(dp[(1 << n) - 1])Cho $0 \le A \le B \le 10^{18}$. Đếm số nguyên trong $[A, B]$ mà trong cách viết thập phân (không có số 0 ở đầu) không có hai chữ số kề nhau nào bằng nhau. Ví dụ 1213 thoả, 1223 không thoả.
1 10090📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
last là chữ số vừa điền, started cho biết đã gặp chữ số khác 0 chưa. Khi chưa started, các số 0 ở đầu chỉ là “đệm”, không được coi là chữ số kề nhau (nếu không, mọi số có ít chữ số hơn $X$ sẽ bị loại oan). Khi đã started, bỏ qua chữ số $d = \text{last}$. Ví dụ: trong 1…100 có 9 số một chữ số, 90 − 9 = 81 số hai chữ số thoả (bỏ 11, 22, …, 99), và 100 bị loại: tổng 90.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
string X;
long long memo[20][11];
bool seen[20][11];
long long f(int pos, int last, bool tight, bool started){
if(pos == (int)X.size()) return 1;
if(!tight && started && seen[pos][last]) return memo[pos][last];
int lim = tight ? X[pos] - '0' : 9;
long long res = 0;
for(int d = 0; d <= lim; d++){
if(started && d == last) continue; // hai chữ số kề nhau bằng nhau
bool ns = started || d != 0;
res += f(pos + 1, ns ? d : 10, tight && d == lim, ns);
}
if(!tight && started){ seen[pos][last] = true; memo[pos][last] = res; }
return res;
}
long long countUpTo(long long x){
if(x < 0) return 0;
X = to_string(x);
memset(seen, 0, sizeof(seen));
return f(0, 10, true, false); // last = 10: chưa có chữ số nào
}
int main(){
long long A, B;
cin >> A >> B;
cout << countUpTo(B) - countUpTo(A - 1);
return 0;
}import sys
from functools import lru_cache
def count_up_to(x):
if x < 0:
return 0
X = str(x)
@lru_cache(maxsize=None)
def f(pos, last, tight, started):
if pos == len(X):
return 1
lim = int(X[pos]) if tight else 9
res = 0
for d in range(lim + 1):
if started and d == last: # hai chữ số kề nhau bằng nhau
continue
ns = started or d != 0
res += f(pos + 1, d if ns else 10, tight and d == lim, ns)
return res
return f(0, 10, True, False) # last = 10: chưa có chữ số nào
A, B = map(int, sys.stdin.read().split())
print(count_up_to(B) - count_up_to(A - 1))Có $n$ trạm ($2 \le n \le 13$) đánh số từ 1. Đi thẳng từ trạm $i$ tới trạm $j$ mất $c_{ij}$ phút ($0 \le c_{ij} \le 10^6$, có thể $c_{ij} \ne c_{ji}$). Xe xuất phát ở trạm 1 và phải kết thúc ở trạm $n$, đi qua mỗi trạm đúng một lần. Tìm tổng thời gian nhỏ nhất.
4
0 1 5 9
3 0 2 8
4 6 0 1
2 2 2 04📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long c[13][13], dp[1 << 13][13];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) cin >> c[i][j];
for(int mask = 0; mask < (1 << n); mask++)
for(int v = 0; v < n; v++) dp[mask][v] = INF;
dp[1][0] = 0; // ở trạm 1 (chỉ số 0)
for(int mask = 1; mask < (1 << n); mask++)
for(int v = 0; v < n; v++){
if(dp[mask][v] == INF || v == n - 1) continue; // trạm n là điểm cuối
for(int u = 0; u < n; u++){
if(mask >> u & 1) continue;
int nm = mask | (1 << u);
dp[nm][u] = min(dp[nm][u], dp[mask][v] + c[v][u]);
}
}
cout << dp[(1 << n) - 1][n - 1];
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
c = [[int(data[1 + i * n + j]) for j in range(n)] for i in range(n)]
INF = float('inf')
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # ở trạm 1 (chỉ số 0)
for mask in range(1, 1 << n):
row = dp[mask]
for v in range(n - 1): # v = n - 1 là điểm cuối, không đi tiếp
cur = row[v]
if cur == INF:
continue
cv = c[v]
for u in range(n):
if mask >> u & 1:
continue
nm = mask | 1 << u
if cur + cv[u] < dp[nm][u]:
dp[nm][u] = cur + cv[u]
print(dp[(1 << n) - 1][n - 1])
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét