Hướng dẫn giải của Ký Ức Vụn Vỡ

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

Hướng tiếp cận

Bài toán yêu cầu tìm đường đi có trọng số lớn nhất trong DAG sao cho dãy ký tự trên đường đi tạo thành palindrome. Ta kết hợp DP trên DAG với ràng buộc palindrome bằng cách duy trì trạng thái hai đầu.

Nhận xét quan trọng

Palindrome mở rộng từ giữa ra ngoài: Một palindrome có thể được xây dựng bằng cách bắt đầu từ trung tâm (1 ký tự cho palindrome lẻ, 2 ký tự giống nhau cho palindrome chẵn) rồi mở rộng bằng cách thêm cùng một ký tự ở cả hai đầu.
Trạng thái DP hai đầu: Ta định nghĩa $d p [u] [v]$ là trọng số lớn nhất của một đường đi palindrome bắt đầu tại đỉnh $u$ và kết thúc tại đỉnh $v$ . Khi mở rộng, ta thêm một đỉnh $u^{'}$ trước $u$ và một đỉnh $v^{'}$ sau $v$ với điều kiện $c_{u^{'}} = c_{v^{'}}$ .
Tính đúng đắn trên DAG: Vì đồ thị là DAG, mọi đường đi đều không lặp đỉnh. Khi mở rộng $(u, v)$ thành $(u^{'}, v^{'})$ , ta có $u^{'}$ đứng trước $u$ và $v^{'}$ đứng sau $v$ trong thứ tự topo, nên $u^{'}$ và $v^{'}$ không thể nằm trên đường đi từ $u$ đến $v$ .
Thứ tự xử lý: Gán mỗi đỉnh một chỉ số theo thứ tự topo. Trạng thái $(u, v)$ có "span" = $t o p o_p o s [v] - t o p o_p o s [u]$ . Ta xử lý các trạng thái theo span tăng dần để đảm bảo mọi trạng thái con đã được tính trước.

Thuật toán

Sắp xếp topo đồ thị DAG. Gán topo_pos[u] cho mỗi đỉnh $u$ .
Khởi tạo:
- $d p [u] [u] = w_{u}$ cho mọi đỉnh $u$ (palindrome độ dài 1).
- $d p [u] [v] = w_{u} + w_{v}$ nếu có cạnh $u \to v$ và $c_{u} = c_{v}$ (palindrome độ dài 2).
Chuyển trạng thái: Duyệt các cặp $(u, v)$ theo span tăng dần. Với mỗi $(u, v)$ có $d p [u] [v] \geq 0$ :
- Với mỗi cạnh u′→u (đỉnh u′ là tiền bối của u) và mỗi cạnh v→v′ (đỉnh v′ là hậu duệ của v):
  - Nếu $c_{u^{'}} = c_{v^{'}}$ : cập nhật $d p [u^{'}] [v^{'}] = max (d p [u^{'}] [v^{'}], d p [u] [v] + w_{u^{'}} + w_{v^{'}})$ .
Đáp án: ${max}_{u, v} d p [u] [v]$ .

Độ phức tạp

Thời gian: $O (N^{2} + \sum_{(u, v) valid} in_deg (u) \times out_deg (v))$ . Trong trường hợp xấu nhất với $M$ cạnh, tổng chuyển trạng thái bị chặn bởi $O (N^{2} \cdot {\bar{d}}^{2})$ với $\bar{d}$ là bậc trung bình. Với $N \leq 1500$ và $M \leq 5000$ , bậc trung bình nhỏ nên thuật toán chạy hiệu quả.
Bộ nhớ: $O (N^{2})$ cho bảng DP.

Bình luận

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