Nguồn: Olympic miền Nam-2011
Ở một vương
quốc nọ có 1 vị vua và ông có N quý phi. Trên miếng đất hình vuông có kích thước
NxN, nhà vua muốn xây dựng cho mỗi quý phi, mỗi người một cung điện (giả sử mỗi
cung điện đều nằm trên một mảnh đất kích thước 1x1). Vấn đề là các quý phi này
có tính ghen ghét nhau nên nhà vua không muốn các cung điện nhìn thấy nhau từ
các hướng (ngang, dọc, chéo).Chi phí xây dựng các
cung điện trên mỗi ô đất có thể có giá thành khác nhau. Nhà vua muốn xây dựng N
cung điện với tổng chi phí thấp nhất.
Yêu cầu: Bạn hãy giúp nhà vua thực hiện công việc đó
Dữ liệu vào: Từ file văn bản CUNGDIEN.INP gồm N+1 dòng
- Dòng đầu chứa số N (1≤N≤16)
- N dòng sau, mỗi dòng chứa N số là chi phí xây dựng tại ô đất
tương ứng (Chi phí xây dựng cung điện trong một ô có giá trị nguyên từ 1 đến
100). Mỗi số cách nhau ít nhất một khoảng trắng
Dữ liệu ra: Ghi ra file văn bản CUNGDIEN.OUT gồm một số duy nhất cho biết tổng chỉ phí thấp nhất cho việc xây dựng. Giả sử dữ liệu luôn có lời giải
Dữ liệu ra: Ghi ra file văn bản CUNGDIEN.OUT gồm một số duy nhất cho biết tổng chỉ phí thấp nhất cho việc xây dựng. Giả sử dữ liệu luôn có lời giải
Ví dụ:
CUNGDIEN.INP
|
CUNGDIEN.OUT
|
4
3 4 12 3
6 1 7 1
2 4 1 5
12 3 8 7
|
15
|
