Mô tả bài toán
Io và Ao chơi một trò chơi trên các từ chỉ gồm các nguyên âm (A, E, I, O, U).
Hai bạn nói luân phiên, sao cho:
- Chữ cái đầu tiên của từ sau phải trùng với chữ cái cuối của từ trước.
- Mỗi từ chỉ được sử dụng tối đa một lần.
- Điểm của trò chơi là tổng độ dài của các từ được nói ra.
Yêu cầu
Cho trước danh sách các từ.
Hãy xác định tổng điểm lớn nhất mà hai bạn có thể đạt được theo quy tắc trên.
Dữ liệu
- Dòng đầu: số nguyên dương $N$ ($1 \le N \le 16$).
- $N$ dòng tiếp theo: mỗi dòng chứa một từ gồm các ký tự
A,E,I,O,U.- Độ dài mỗi từ $\le 100$.
- Mỗi từ là duy nhất.
Kết quả
In ra một số nguyên duy nhất – tổng độ dài lớn nhất có thể đạt được.
Phân tích và ý tưởng thuật toán
a) Xây dựng đồ thị $G$
Ta mô hình bài toán bằng một đồ thị có hướng:
- Tập đỉnh: mỗi từ là một đỉnh.
- Trọng số đỉnh: độ dài của từ tương ứng.
- Cạnh có hướng: tồn tại cạnh từ $u \to v$ nếu ký tự cuối của $u$ trùng với ký tự đầu của $v$.
Bước dựng đồ thị có độ phức tạp $O(N^2)$.
b) Tìm đường đi dài nhất trên đồ thị
Vì $N \le 16$, ta có thể duyệt toàn bộ các tập con của đỉnh bằng kỹ thuật quy hoạch động bitmask (bitmask DP).
Gọi:
- $mask$ là một số nhị phân gồm $N$ bit, bit $k = 1$ nếu đỉnh $k$ đã được dùng.
- $f[mask][k]$ là độ dài lớn nhất của một đường đi hợp lệ,
sử dụng đúng các đỉnh trong $mask$, và kết thúc tại đỉnh $k$.
Công thức quy hoạch động
Với mọi trạng thái hợp lệ $f[mask][k]$, xét đỉnh $k’$ (bit $k’$ của $mask$ bật) sao cho có cạnh $k’ \to k$:
$$f[mask][k] = \max \big( f[mask \setminus {k}][k’] + len[k] \big)$$
Trong đó:
- $len[k]$ là độ dài của từ thứ $k$.
- $mask \setminus {k}$ tức là tắt bit $k$ trong $mask$.
Khởi tạo:
$$
f[1 << k][k] = len[k]
$$
vì đường đi chỉ gồm duy nhất một từ.
Kết quả cuối cùng:
$$
ans = \max_{mask,k} f[mask][k]
$$
Độ phức tạp
- Số trạng thái: $2^N \times N$.
- Mỗi trạng thái xét $N$ chuyển: tổng cộng $O(N^2 \times 2^N)$.
- Với $N \le 16$, chương trình chạy rất nhanh.
Lời giải tham khảo
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<string> w(N);
for (int i = 0; i < N; ++i) cin >> w[i];
vector<int> len(N);
vector<char> first(N), last(N);
for (int i = 0; i < N; ++i) {
len[i] = w[i].size();
first[i] = w[i].front();
last[i] = w[i].back();
}
// Tạo cạnh kề: adj[u][v] = true nếu last(u) = first(v)
vector<vector<bool>> adj(N, vector<bool>(N, false));
for (int u = 0; u < N; ++u)
for (int v = 0; v < N; ++v)
if (u != v && last[u] == first[v])
adj[u][v] = true;
int FULL = 1 << N;
vector<vector<int>> dp(FULL, vector<int>(N, -1e9));
// Khởi tạo
for (int k = 0; k < N; ++k)
dp[1 << k][k] = len[k];
// Quy hoạch động
for (int mask = 0; mask < FULL; ++mask) {
for (int u = 0; u < N; ++u) if (dp[mask][u] >= 0) {
for (int v = 0; v < N; ++v)
if (!(mask & (1 << v)) && adj[u][v]) {
int nmask = mask | (1 << v);
dp[nmask][v] = max(dp[nmask][v], dp[mask][u] + len[v]);
}
}
}
int ans = 0;
for (int mask = 0; mask < FULL; ++mask)
for (int k = 0; k < N; ++k)
ans = max(ans, dp[mask][k]);
cout << ans << "\n";
}
Ví dụ
WORDS.INP 3 AEIOU UIU EO
- Có cạnh
AEIOU → UIU(U = U). - Có cạnh
UIU → ...không nối được. - Có cạnh
EO → ...không nối được.
Đường đi tốt nhất: AEIOU → UIU, tổng độ dài = $5 + 3 = 8$.
WORDS.OUT 8
Kết luận
Bài toán “Chơi chữ” là ví dụ điển hình cho việc:
- Biểu diễn bài toán bằng đồ thị.
- Sử dụng quy hoạch động trên tập con (bitmask DP) để tìm đường đi dài nhất.
Kỹ thuật này rất phổ biến trong các bài toán dạng Hamilton Path / Bitmask DP trong lập trình thi đấu.