Quy hoạch động bài FROG 2 - Atcoder
Frog2 là một bài tập Quy hoạch động cơ bản dạng dễ. Bài này được nằm trong loạt bài mẫu nhằm giúp các bạn định hướng cách nghĩ để có thể đưa ra một thuật toán Quy hoạch động. Ở đó bao gồm các bước tư duy nhằm định nghĩa một hàm Quy hoạch động (hàm trạng thái), một công thức Quy hoạch động, các bài toán cơ sở, bảng phương án và các lưu ý khi tính bảng phương án.
Bài Frog 2 có thể tóm tắt như sau: Có N hòn đá được đánh số từ 1 tới N. Hòn đá thứ i có độ cao h_i. Ban đầu chú ếch ở hòn đá 1. Chú liên tục thực hiện một loạt hành động sau: Nếu chú đang ở hòn đá i, chú có thể nhảy tới các hòn đá i+1, i+2,..., i+K và chi phí cho bước nhảy đó là |H_i - H_j| với j là hòn đá mà chú ếch nhảy tới. Hỏi chi phí tối thiểu để chú ếch nhảy từ hòn đá đầu đến hòn đá thứ N?
Nếu đã làm bài Frog 1 rồi thì bạn sẽ nhận thấy ngay Frog 2 là bài khá tương tự bài Frog 1. Như vậy, cách nghĩ và cách phân tích để đưa ra phương án Quy hoạch động cũng tương tự bài Frog 1. Bạn có thể thực hành nghĩ lại theo các chỉ dẫn dưới đây. Sau đó bạn hãy đối chiếu với cách phân tích của tôi ở phía cuối bài viết.
Bước 1. Định nghĩa một trạng thái (hàm quy hoạch động). Ta gọi một hàm F(...) xác định một trạng thái bài toán, vậy trạng thái đó phụ thuộc vào tham số nào? Bài toán QHĐ được xem như một dãy các bước chuyển trạng thái, nên bạn có thể nghĩ đến trạng thái đầu tiên là gì, phụ thuộc và yếu tố nào?
Bước 2. Xác định công thức Quy hoạch động. Giả sử đang ở trạng thái i nào đó, tại đó hàm trạng thái là F(i,...)? Để có thể tới được trạng thái i thì có thể đi từ trạng thái nào đó ngay phía trước nó? F(j...) F(k,...) nào ngay trước đó? Và để chuyển tới được trạng thái i từ trạng thái trước đó, thì hàm trạng thái F(i,..) liên hệ với F(j,...) F(k,...) như thế nào? Mối liên hệ này sẽ cho phép tính được các trạng thái sau nhờ các trạng thái phía trước nó.
Bước 3. Tìm các cơ sở quy hoạch động. Là các trạng thái mà dễ dàng tính được giá trị. Có thể là trạng thái đầu, trạng thái cuối, hay trạng thái ảo nào đó (trước cả trạng thái đầu, sau cả trạng thái cuối). Bạn thử tính bằng cách phân tích logic bài toán, giảm các tham số về nhỏ nhất xem trạng thái đầu tiên như thế nào?
Bước 4. Lập bảng phương án. Lưu trữ các giá trị trạng thái bằng mảng. Cách tính mảng đó dựa vào mối liên hệ trong công thức Quy hoạch động. Vậy có thể lưu các trạng thái đó bằng mảng mấy chiều? Và thứ tự tính toán thế nào?
Bước 5. Thông báo kết quả. Sau khi tính được bảng phương án, bạn hãy xác định xem kết quả bài toán là gì dựa vào bảng phương án vừa tính được đó?
Như thế, qua 5 bước trên về cơ bản là bạn đã có một thuật toán được thiết kế theo mô hình Quy hoạch động. Hãy thử check lại và so sánh với cách nghĩ của tôi.
Bước 1: Giả sử con ếch ở trạng thái i nào đó, như vậy ta cần tính chi phí nhỏ nhất để có thể từ hòn đá 1 tới hòn đá i. Chi phí đó chính là hàm trạng thái cần tính, và mỗi trạng thái ấy chỉ phụ thuộc vào 1 tham số là i. Vậy ta gọi hàm F(i) là chi phí nhỏ nhất để con ếch đi từ hòn đá 1 tới hòn đá i. Và như thế, kết quả cần tính sẽ là F(n) - chi phí nhỏ nhất để con ếch đi tới hòn đá N.
Bước 2. Giả sử con ếch đang ở hòn đá i, chi phí đến đó là F(i); ta chưa cần tính gì cả, chỉ biết là có F(i) tại đó. Để tới được trạng thái i, con ếch có thể nhảy từ các hòn đá (i-1), (i-2),...,(i-k) nếu (i-k)>=1; Như vậy, chi phí F(i) sẽ là chi phí nhỏ nhất giữa các F(j)+|H_i - H_j| với j từ 1 tới k.
Bước 3. Cơ sở quy hoạch động là F(1)=0;
Bước 4. Bảng phương án. Dễ thấy là khi hàm F chỉ phụ thuộc 1 tham số thì chỉ cần lưu mảng 1 chiều. Điền trước mảng các giá trị F[1] đã tính sẵn rồi, sử dụng vòng for để tính các F[i] còn lại thôi. Và kết quả cần tìm là F[N] nhỉ?
Code mẫu tham khảo bài FROG 2 - Atcoder
int min_of_al_J = 1e9;
for (int j = 1; j <= k; j ++)
if (i - j >= 1)
min_of_al_J = min(min_of_al_J, F[i - j] + abs(h[i] - h[i - j]));
F[i] = min_of_al_J;
}
Comments
Post a Comment