Ký Ức Vụn Vỡ

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

1. 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.

2. Trạng thái DP hai đầu: Ta định nghĩa $dp[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^{\prime }$ trước $u$ và một đỉnh $v^{\prime }$ sau $v$ với điều kiện $c_{u^{\prime }}=c_{v^{\prime }}$.

3. 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^{\prime },v^{\prime })$, ta có $u^{\prime }$ đứng trước $u$ và $v^{\prime }$ đứng sau $v$ trong thứ tự topo, nên $u^{\prime }$ và $v^{\prime }$ không thể nằm trên đường đi từ $u$ đến $v$.

4. 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" = $topo\_pos[v]-topo\_pos[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

1. Sắp xếp topo đồ thị DAG. Gán topo_pos[u] cho mỗi đỉnh $u$.

2. Khởi tạo:

   • $dp[u][u]=w_u$ cho mọi đỉnh $u$ (palindrome độ dài 1).
   • $dp[u][v]=w_u+w_v$ nếu có cạnh $u\to v$ và $c_u=c_v$ (palindrome độ dài 2).

3. 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ó $dp[u][v]\ge 0$:

   • Với mỗi cạnh $u^{\prime }\to u$ (đỉnh $u^{\prime }$ là tiền bối của $u$) và mỗi cạnh $v\to v^{\prime }$ (đỉnh $v^{\prime }$ là hậu duệ của $v$):
     • Nếu $c_{u^{\prime }}=c_{v^{\prime }}$: cập nhật $dp[u^{\prime }][v^{\prime }]=max(dp[u^{\prime }][v^{\prime }],dp[u][v]+w_{u^{\prime }}+w_{v^{\prime }})$.

4. Đáp án: ${max}_{u,v}dp[u][v]$.

Độ phức tạp

• Thời gian: $O(N^2+{\sum }_{(u,v)\text{ valid}}\text{in\_deg}(u)\times \text{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·{\overline{d}}^2)$ với $\overline{d}$ là bậc trung bình. Với $N\le 1500$ và $M\le 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.