Combo Trò Chơi

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

1. 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.
2. 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.
3. 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.
4. Số nút automaton tối đa: $N\times |S_i{|}_{max}+1=20\times 15+1=301$.

Thuật toán

1. 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.
2. 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.
3. 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])
4. Đáp án: ${max}_{s}dp[K][s]$.

Độ phức tạp

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