Bình luận

• 
  

  0

  

  giabao8a70409042008  đã bình luận lúc 15, Tháng 8, 2023, 12:32

  Mình xin phép chia sẻ thuật của bài này ạ.

  Phương pháp: Quy hoạch động bitmask (Mình biết là còn có cách tốt hơn là tìm bộ ghép cực đại của đồ thị 2 phía có trọng số cực tiểu nhưng do mình không biết nên dùng đỡ cách này)

  Đầu tiên gọi ~cost[i][j]~ là chi phí để di chuyển con hậu ban đầu ở hàng i (ở ô (~i~, ~a[i]~)) đến con hậu cần đến ở hàng j (ở ô (~j~, ~b[j]~)) (Tính bằng khoảng cách Manhattan)

  Như vậy ta cần tìm 1 hoán vị các số từ 1 -> n là ~p[1]~, ~p[2]~, ..., ~p[n]~ sao cho ~cost[1][p[1]]+cost[2][p[2]]+...+cost[n][p[n]]~ nhỏ nhất (tức là sao cho tổng chi phí để di chuyển con hậu ban đầu ở hàng i đến con hậu cần đến ở hàng ~p[i]~ là nhỏ nhất)

  Ta coi việc mình chọn con hậu ban đầu ở hàng i đến con hậu cần đến ở hàng ~p[i]~ là việc bắt cặp (i, ~p[i]~)

  Xét i hàng đầu tiên, 1 trạng thái là 1 tập hợp i số (~p[1]~, ~p[2]~, ..., ~p[i]~) sao cho ta có các cặp (1, ~p[1]~), (2, ~p[2]~), ..., (i, ~p[i]~)

  Ta có thể biểu diễn trạng thái đó bằng 1 con số (gọi là State), trong đó nếu ~p[i]~ có trong trạng thái đó thì bit thứ ~i-1~ trong biểu diễn nhị phân của State là 1, ngược lại là 0.

  VD: Giả sử ta có bảng cost sau:

  2 1 5 4

  2 1 3 2

  2 3 1 2

  4 5 1 2

  Xét 2 hàng đầu tiên, ta có một trạng thái (2, 3) -> Khi đó State = 0110 = 6. Ta cũng có một trạng thái có State = 6 là (3, 2) -> 2 trạng thái có cùng hoán vị thì có cùng giá trị State.

  Ở trạng thái 1, ta có chi phí là ~cost[1][2]+cost[2][3]=4~

  Ở trạng thái 2, ta có chi phí là ~cost[1][4]+cost[2][3]=6~

  Vậy trong các trạng thái có State = 6 thì trạng thái 1 cho ra chi phí thấp hơn.

  Khi đó gọi dp[State] là chi phí nhỏ nhất trong tất cả các trạng thái có giá trị là State

  Ta dễ dàng nhận ra với mọi số State đều được biểu diễn dưới dạng số nhị phân bằng 1 cách duy nhất.

  Từ đó ta cũng dễ thấy rằng số bit 1 trong biểu diễn nhị phân của State cũng sẽ tương ứng với chỉ số hàng ta đang xét. Gọi r = số bit 1 trong biểu diễn nhị phân của State

  Nếu bit thứ m của State bằng 1 (trong trạng thái có m) thì ta có ~dp[State]~ = ~dp[State~ xor ~(1 << m)]~ + ~cost[r][m]~

  Khi đó ta có công thức để tính chi phí nhỏ nhất: ~dp[State]~ = min(~dp[State~ xor ~(1 << m)]~ + ~cost[r][m]~), với r = số bit 1 trong biểu diễn nhị phân của State, State & (1<<m) = (1<<m) (Tức là trạng thái có giá trị là (1<<m) là tập con của trạng thái có giá trị là State).

  Đáp án cho bài toán này là dp[(1<<n) - 1];

  Chúc các bạn một ngày vui vẻ! <3