[Chuyên đề] Quy hoạch động (Nâng cao: Trạng thái - Vị trí - Cấu hình)

DP BITMARK 1: (DP trạng thái)
Là 1 phương pháp :
Giải quyết tốt nhiều bài toán yêu cầu sử lý nhiều lớp về trạng thái
ứng dụng khá quan trọng trong nhiều bài toán có dữ liệu có thể đua về xử lí bằng bit
là 1 pp khá hay, có thể thay thế 1 số bài toán về pp nhánh cận
cũng có thể nói rằng, dp bitmask là 1 cách vét thông minh và có độ chính xác cao.
Trong pp này, ta cần lưu ý :
Các bài toán con được lưu trong 1 mảng, gọi là bảng trạng thái. Trạng thái hiện tại sẽ cập nhật dữ liệu của trạng thái trước.
Phải biết cập nhật tất cả các trạng thái trước.
Ví dụ : 00000110011000 sẽ là bài toán trước của 00000110011010
Sử dụng pp về xử lý bit để giải quyết.
Có thể giải nhiều bài toán về phép đếm với cấu hình nhỏ.
Phân loại : có 2 loại chính :
Loại thứ 1 : là loại mà cấu hình vị trí của giá trị hok bị thay đổi – tức là cách chọn cố định
Loại thứ 2 : là loại mà phụ thuôc vào cách xếp thứ tự giá trị để bài toán tối ưu
Thông thường, bảng sẽ xây dựng được như sau :
F[x] – chỉ lưu giá trị tại trạng thái x – chủ yếu dùng là cho loại 1
F[x,I] – lưu giá trị tại trạng thái x với I nạp vô sau cùng
Ví dụ : cho n phần tử, tìm k phần tử sao cho tổng k phần tử bé hơn số C cho trước
Giải : Theo pp như trên đã trình bày, thì ta sẽ xây dựng bài toán từ các trạng thái trước cho nên công thức là : f[x] := f[x’] + a[i] (với x’ là trạng thái trước của k, khi thêm giá trị a[i] vào (tức là trạng thái bit I – 1 của x’ là 1) thì ta có dc trạng thái x). ta tính cho tới khi x = 1 shl n – 1 (tức là xét tất cả n phần tử)
Problem :
QBSELECT vn.spoj.pl/problems/QBSELECT/
QBGAME vn.spoj.pl/problems/QBGAME/
LEM3 vn.spoj.pl/problems/LEM3/
MIXUP2 vn.spoj.pl/problems/MIXUP2/
COWGIRL vn.spoj.pl/problems/COWGIRL/

DP VỊ TRÍ – CẤU HÌNH :
Đây là 1 dạng bài toán thường yêu cầu giải quyết 2 bài toán sau :
Bài toán 1 : cho vị trí k , hãy ghi ra cấu hình tại vị trí k ấy
Bài toán 2 : cho 1 cấu hình, hãy ghi ra vị trí k mà cấu hình ấy đạt được
Pp làm chính như sau :
Thông thường phần khởi tạo, ta sẽ gán vào mảng cấu hình cao nhất khi đạt tới vị trí ấy
Vào phần dp , ta giải quyết 2 vấn đề trên bằng cách :
Bài toán 1 : ta thu hẹp từ điển cấu hình (tức là bỏ hết những cấu hình nằm trước cấu hình k) , dồng thời cập nhật lại vị trí cấu hình k khi loại bỏ các cấu hình trước nó.
Bài toán 2 : ta tìm số lượng các cấu hình nằm trước cấu hình cần tìm, từ đó suy ra vị trí của cấu hình đang xét
Ví dụ:
Cho 1 tập từ điển gồm các dãy nhị phân có n phần tử, yêu cầu :
Tìm vị trí của 1 cấu hình cho trước
Cho vị trí, tìm cấu hình tại vị trí ấy
Với bài này , ta làm như sau :
Phần init, theo pp làm thì ta phải đếm số cấu hình cao nhất tại vị trí k, nên tại vị trí k có cấu hình là f[k] := 2^k
F[0] := 1;
For I := 1 to n do f[i] := 2*f[I – 1];
Yêu cầu 1 : ta sẽ đếm những cấu hình đứng trước cấu hình k đang xét. Những cấu hình cần đếm là những cấu hình mà nhỏ hơn k
Ví dụ :
xxxxxxxx1xxxxxxxx : cấu hình của k
xxxxxxxx0xxxxxxxx : tại vị trí đang xét
Do đó phải có f[I – 1] cấu hình nhỏ hơn vị trí I đang xét
Sau khi đếm xong số lượng cái dãy nhị phân bé hơn k, ta phải + 1
For I := 1 to n do
If s[i] = 1 then res := res + f[I – 1];
Yêu cầu 2 : cách lập luận giống như yêu cầu 1, đồng thời phải cập nhật lại cho vị trí k có vị trí mới :

Code:


For I := 1 to n do
  If k >= f[n – i] then c[i] := 0
  Else
    Begin
      C[i] := 1;
      K := k – f[n – i];
    End;
For I := 1 to n do writeln(c[i]);


Problem :
SHHV vn.spoj.pl/problems/SHHV/
SHTH vn.spoj.pl/problems/SHTH/
CATALAN vn.spoj.pl/problems/CATALAN/