Ký Ức Vụn Vỡ

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.5s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Giáo sư Gilderoy Lockhart thầy giáo Phòng Chống Nghệ Thuật Hắc Ám tại Hogwarts - vừa thực hiện một Bùa Xóa Trí Nhớ (Memory Charm) thất bại thảm hại. Thay vì xóa trí nhớ của mục tiêu, lời nguyền đã phản ngược lại và phá vỡ chính ký ức của Lockhart thành $N$ mảnh vỡ.

Mỗi mảnh ký ức $i$ mang một ký tự đặc trưng $c_{i}$ (chữ cái thường Latin) và một giá trị cảm xúc $w_{i}$ . Các mảnh ký ức được liên kết với nhau theo $M$ kết nối một chiều, tạo thành một đồ thị có hướng không chu trình (DAG): nếu có kết nối từ mảnh $u$ đến mảnh $v$ , thì mảnh $u$ là tiền đề để nhớ lại mảnh $v$ .

Giáo sư Dumbledore muốn giúp Lockhart khôi phục lại một chuỗi ký ức có ý nghĩa. Một chuỗi ký ức là một đường đi trong đồ thị (theo chiều các cạnh). Chuỗi ký ức được coi là có ý nghĩa nếu dãy ký tự đặc trưng của các mảnh trên đường đi tạo thành một xâu đối xứng (palindrome).

Dumbledore muốn tìm chuỗi ký ức có ý nghĩa với tổng giá trị cảm xúc lớn nhất.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ( $1 \leq N \leq 1500$ , $0 \leq M \leq 5000$ ) — số mảnh ký ức và số kết nối.
$N$ dòng tiếp theo, dòng thứ $i$ chứa một ký tự $c_{i}$ và một số nguyên $w_{i}$ ( $1 \leq w_{i} \leq 10^{9}$ ) — ký tự đặc trưng và giá trị cảm xúc của mảnh ký ức thứ $i$ .
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ( $1 \leq u, v \leq N$ , $u \neq v$ ) — biểu thị một kết nối từ mảnh $u$ đến mảnh $v$ .

Đồ thị đảm bảo là DAG (không có chu trình). Không có cạnh trùng lặp.

Dữ liệu ra

In ra một số nguyên duy nhất - tổng giá trị cảm xúc lớn nhất của một chuỗi ký ức có ý nghĩa (đường đi palindrome).

Ràng buộc

$1 \leq N \leq 1500$
$0 \leq M \leq 5000$
$1 \leq w_{i} \leq 10^{9}$
$c_{i}$ là chữ cái thường Latin ('a' - 'z')
Đồ thị là DAG, không có cạnh trùng lặp
Đường đi có thể có độ dài $1$ (chỉ một đỉnh duy nhất)

Ví dụ

Input	Output	Giải thích
5 6 a 3 b 5 c 2 a 4 b 1 1 2 1 3 2 4 2 5 3 4 3 5	12	Chọn đường đi $1 \to 2 \to 4$ với ký tự "aba" (palindrome), tổng giá trị = $3 + 5 + 4 = 12$ . Đây là đường đi palindrome có trọng số lớn nhất.
4 4 a 10 b 1 a 8 b 2 1 2 1 3 2 4 3 4	18	Chọn đường đi $1 \to 3$ với ký tự "aa" (palindrome), tổng giá trị = $10 + 8 = 18$ . Dù đường đi $1 \to 2 \to 4$ dài hơn nhưng "abb" không phải palindrome.

Bình luận

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