Hướng dẫn giải của Combo Trò Chơi

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Combo Tối Đa

Hướng tiếp cận

Xây dựng Aho-Corasick automaton từ $N$ chuỗi combo, rồi dùng quy hoạch động trên automaton để tìm chuỗi $K$ ký tự (gồm A, B, C) cho điểm tối đa.

Nhận xét quan trọng

Aho-Corasick cho phép khớp tất cả các chuỗi combo đồng thời khi duyệt qua từng ký tự nhấn. Mỗi trạng thái (nút) của automaton đại diện cho một "hậu tố" của chuỗi đã nhấn.
Tại mỗi nút $s$ , giá trị val[s] lưu số combo kết thúc tại đây (bao gồm cả suffix links), được tích lũy khi xây dựng automaton.
Trạng thái DP: dp[k][s] = điểm tối đa khi đã nhấn $k$ phím và đang ở nút $s$ của automaton. Khởi tạo dp[0][0] = 0.
Số nút automaton tối đa: $N \times | S_{i} |_{max} + 1 = 20 \times 15 + 1 = 301$ .

Thuật toán

Xây trie từ $N$ chuỗi combo, đánh dấu val[node]++ tại nút kết thúc mỗi chuỗi.
Xây suffix links (failure links) bằng BFS (Aho-Corasick build). Khi build, cộng dồn val[u] += val[fail[u]] để tính điểm suffix.
DP: với mỗi bước k từ 0 đến K−1, mỗi trạng thái s, thử 3 ký tự A/B/C:
- Trạng thái tiếp theo: ns = ch[s][c]
- Điểm mới: dp[k+1][ns] = max(dp[k+1][ns], dp[k][s] + val[ns])
Đáp án: ${max}_{s} d p [K] [s]$ .

Độ phức tạp

Thời gian: $O (N \cdot L + K \cdot | V | \cdot 3)$ với $| V | \leq 301$ nút, $L \leq 15$ độ dài combo
Bộ nhớ: $O (K \cdot | V |)$

Bình luận

Không có bình luận tại thời điểm này.