V8SORT spoj – sắp xếp

Nguồn đề bài: http://vn.spoj.com/problems/V8SORT/

1. Đề bài V8SORT spoj

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à Cij.

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 Cij, 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 ≤ Cij ≤ 999, Cii=0 và Cij=Cji.

Kết quả

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ụ

Dữ liệuKết quả
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
4

2. Gợi ý V8SORT spoj

Ta để ý, số phần tử không quá 7.

Có bạn bảo là quay lui. Nhưng mình vẫn chưa nghĩ ra phải quay thế nào và khi nào thì dừng lại.

Ở đây mình gợi ý giải bằng phương pháp đồ thị. Ta đưa về bài toán tìm đường đi ngắn nhất với trọng số không âm. Sử dụng Dijkstra.

Ví dụ test mẫu, ta coi trạng thái dãy 1,2,3,4,6,5 là một đỉnh có chỉ số 123465 thì đỉnh kề với nó có thể là 213465(chi phí c12) , 321465(chi phí c13), 423165(chi phí c14),… (đổi chỗ 2 kí tự).

Để xây dựng được đồ thị, ta cần nén dãy ban đầu lại thành n phần tử có giá trị từ 1 -> n

=> sắp xếp để dãy thành 1,2,3,4,…,n. Sau đó ta chuyển trạng thái của dãy thành 1 đỉnh có chỉ số tạo thành bởi cách viết liên tiếp dãy đó. Để chuyển thì các bạn có thể viết 1 hàm riêng hoặc trong C có thể sử dụng hàm có sẵn. Vì n<=7 nên ta có max là 7654321 đỉnh.

3. Code mẫu V8SORT spoj

One thought on “V8SORT spoj – sắp xếp

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *