Combo chiến đấu

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

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

Cho xâu $S$ gồm $N$ ký tự (dùng $M$ chữ cái đầu). Có thể đổi ký tự $i$ thành $j$ với chi phí $a [i] [j]$ . Cần biến $S$ thành xâu mà mọi đoạn ký tự giống nhau liên tiếp đều có độ dài $\geq K$ . Tìm chi phí tối thiểu.

Dữ liệu vào

Dòng đầu: $N$ , $M$ , $K$ .
Dòng thứ hai: xâu $S$ .
$M$ dòng tiếp: ma trận chi phí $M \times M$ ( $a [i] [i] = 0$ ).

Dữ liệu ra

Chi phí tối thiểu.

Ràng buộc

$1 \leq N \leq 10^{5}$
$1 \leq M \leq 26$
$1 \leq K \leq N$
$0 \leq a [i] [j] \leq 1000$

Ví dụ

Input	Output	Giải thích
5 5 2 abcde 0 1 4 4 4 2 0 4 4 4 6 5 0 3 2 5 5 5 0 4 3 7 0 5 0	5	Đổi thành "bbccc": a→b (1), d→e→c (2+0=2 qua Floyd), e→c (2). Tổng 5.

Bình luận

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