Đội Hợp Xướng Hogwarts

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.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ư Filius Flitwick đang chuẩn bị cho buổi biểu diễn của Đội Hợp Xướng Hogwarts. Ông cần sắp xếp các ca sĩ vào một đội hình dạng lưới $N \times M$ (gồm $N$ hàng và $M$ cột).

Mỗi ca sĩ thuộc một trong $K$ loại giọng hát (đánh số từ $1$ đến $K$ ). Khi hai ca sĩ đứng cạnh nhau (chung cạnh theo chiều ngang hoặc dọc), sẽ phát sinh một độ bất hòa âm phụ thuộc vào loại giọng của họ. Cụ thể, nếu ca sĩ loại giọng $a$ đứng cạnh ca sĩ loại giọng $b$ , độ bất hòa âm là $D_{a, b}$ .

Ma trận bất hòa âm $D$ có kích thước $K \times K$ và không nhất thiết đối xứng - nghĩa là $D_{a, b}$ có thể khác $D_{b, a}$ . Độ bất hòa âm giữa hai ô kề nhau được tính từ ô bên trái sang phải (theo chiều ngang) và từ ô bên trên xuống dưới (theo chiều dọc). Cụ thể:

Với hai ô $(i, j)$ và $(i, j + 1)$ : bất hòa âm là $D_{g_{i, j}, g_{i, j + 1}}$
Với hai ô $(i, j)$ và $(i + 1, j)$ : bất hòa âm là $D_{g_{i, j}, g_{i + 1, j}}$

trong đó $g_{i, j}$ là loại giọng được gán cho ô $(i, j)$ .

Giáo sư Flitwick muốn gán mỗi ô trong lưới một loại giọng (mỗi loại giọng có thể được dùng nhiều lần) sao cho tổng độ bất hòa âm giữa tất cả các cặp ô kề nhau là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $N$ , $M$ , $K$ - kích thước lưới và số loại giọng hát.
$K$ dòng tiếp theo, mỗi dòng chứa $K$ số nguyên, mô tả ma trận bất hòa âm $D$ . Dòng thứ $a$ ( $1 \leq a \leq K$ ), số thứ $b$ là $D_{a, b}$ .

Dữ liệu ra

In ra một số nguyên duy nhất - tổng bất hòa âm nhỏ nhất có thể đạt được.

Ràng buộc

$1 \leq N \leq 1000$
$1 \leq M \leq 7$
$1 \leq K \leq 4$
$0 \leq D_{a, b} \leq 1000$

Ví dụ

Input	Output	Giải thích
3 3 3 5 2 8 3 4 1 7 6 3	24	Một cách gán tối ưu cho lưới $3 \times 3$ : hàng 1 = (2, 1, 2), hàng 2 = (1, 2, 3), hàng 3 = (2, 3, 3). Tổng bất hòa âm của tất cả 12 cặp kề nhau bằng 24.
2 3 3 5 2 8 3 4 1 7 6 3	13	Lưới $2 \times 3$ với gán: hàng 1 = (1, 2, 3), hàng 2 = (2, 3, 3). Tổng bất hòa âm gồm 7 cặp kề nhau bằng 13.

Ghi chú

Loại giọng được đánh số từ 1 đến $K$ . Ma trận $D$ không nhất thiết đối xứng, nghĩa là bất hòa âm phụ thuộc vào hướng (trái-phải, trên-dưới). Mỗi loại giọng có thể được dùng cho bất kỳ số ô nào.

Bình luận

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