V8SORT - Sắp xếp
Giới hạn- Thời gian: 0.225s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một dãy số. Bạn cần sắp xếp dãy số bằng cách đổi chỗ các cặp phần tử. Chi phí để đổi chỗ phần tử hai ở vị trí i và vị trí j là C ij .
Nhiệm vụ của bạn là tìm chi phí nhỏ nhất để có thể sắp xếp dãy số theo thứ tự tăng dần.
Dữ liệu
- Dòng đầu tiên chứa dãy số cần sắp xếp, có số phần tử không vượt quá 7.
- Dòng thứ i trong số N dòng tiếp theo chứa N số nguyên, số thứ j cho biết C ij , chi phí để đổi chỗ phần tử ở vị trí thứ i và vị trí thứ j. Biết N là số phần tử của dãy số, các phần tử được đánh số từ 1 đến N từ trái sang phải. 0 ≤ C ij ≤ 999, C ii =0 và C ij =C ji .
Kết qủa
In ra một số nguyên dương duy nhất: tổng chi phí nhỏ nhất để sắp xếp dãy số theo thứ tự tăng dần.
Ví dụ
Input
1 2 3 4 6 5 0 1 2 3 4 5 1 0 1 2 3 4 2 1 0 1 2 3 3 2 1 0 1 2 4 3 2 1 0 900 5 4 3 2 900 0
Output
4
- Người up: paulmcvn
- Nguồn bài: Russian Training / vCoder.08