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à 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ố ...
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ệu | Kế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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include <bits/stdc++.h> using namespace std; typedef pair<int,int> II; char s[7]; int a[10],n,f[7654325],x[10],cl[7654325],c[10][10]; set<II> q; int taoso() { int u=0; for(int i=1; i<=n; i++) u=u*10+a[i]; return u; } int taoen() { int u=0; for(int i=1; i<=n; i++) if(a[i]) u=u*10+i; else u=u*10; return u; } bool ok(int u,int i,int j) { if(i==j) return 0; sprintf(s,"%d",u); if(s[i-1]=='0'||s[j-1]=='0') return 0; return 1; } int doi(int u,int i,int j) { sprintf(s,"%d",u); swap(s[i-1],s[j-1]); sscanf(s,"%d",&u); return u; } void dij() { int u,v; II t; int st=taoso(); int en=taoen(); cl[st]=1; f[st]=0; q.insert(II(0,st)); while(!q.empty()) { t=*q.begin(); q.erase(t); u=t.second; if(u==en) { printf("%d",f[u]); return; } for(int i=1; i<=7; i++) for(int j=1; j<=7; j++) if(ok(u,i,j)) { v=doi(u,i,j); if(cl[v]==0) { cl[v]=1; f[v]=f[u]+c[i][j]; q.insert(II(f[v],v)); } else if(f[v]>f[u]+c[i][j]) { q.erase(II(f[v],v)); f[v]=f[u]+c[i][j]; q.insert(II(f[v],v)); } } } } int main() { //freopen("v8sort.inp","r",stdin); ios::sync_with_stdio(0); n=0; gets(s); char* st=strtok(s," "); while(st!=NULL) { sscanf(st,"%d",&a[++n]); x[n]=a[n]; st=strtok(NULL," "); } sort(x+1,x+n+1); for(int i=1; i<=n; i++) a[i]=lower_bound(x+1,x+n+1,a[i])-x; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",&c[i][j]); while(n<7) a[++n]=0; dij(); } |
