Wtc

[NothingToLost]

Thanks vì anh bete vì đã chứng minh đường đi .... nhưng theo em nếu dùng quy hoạch động hay đệ quy thì vẫn tốn quá nhiều thời gian để duyệt .... có ai có cách nào hay hơn không.

[bete]

Thân gửi NothingToLost: tui nghĩ qui hoạch động thì sẽ nhanh hơn duyệt (vét cạn) nhiều lắm

Đặt:
T_lửa: thời gian để lửa cháy hết 1 tầng (10 phút)
T_thang_máy: thời gian để thang máy đi qua 1 tầng (1 phút)
T_ngừng: thời gian để ngừng lại và vét tiền ở 1 tầng (15 phút)
V[i]: số tiền có ở tầng thứ i

Giả sử mình đang ở tầng thứ i (trên đường đi xuống).
Giả sử thêm là lúc đó lửa đang cách nơi mình đang đứng là x tầng (x không bắt buộc là số nguyên)

=> mình sẽ có 2 lựa chọn:

a) đi xuống tầng (i-1) mà không ngừng lại (đi xuống tiếp tầng (i-2)). Khi mình xuống tới tầng thứ (i-1) thì khoảng cách x:
- tăng thêm 1 (mình rời xa ngọn lửa thêm 1 tầng)
- giảm đi (T_thang_máy/T_lửa) (lửa đã cháy xuống thêm 1 chút)
Tức là x trở thành (x + 1 - T_thang_máy/T_lửa)

b) đi xuống tầng (i-1) và ngừng lại lấy tiền ở tầng này. Khi mình xuống tới tầng thứ (i-1) và lấy tiền ở tầng này xong thì khoảng cách x:
- tăng thêm 1 (mình rời xa ngọn lửa thêm 1 tầng)
- giảm đi (T_thang_máy/T_lửa) (lửa đã cháy xuống thêm 1 chút)
- giảm đi (T_ngừng/T_lửa) (lửa đã cháy xuống thêm 1 chút)
Tức là x trở thành (x + 1 - T_thang_máy/T_lửa - T_ngừng/T_lửa)

Như vậy nếu mình đặt hàm F(i,x) thỏa:
- input: mình đang ở tầng i, lửa cách mình 1 khoảng là x tầng
- output: tổng số tiền lớn nhứt có thể lấy được nếu mình bắt đầu đi xuống và lấy tiền ở các tầng dưới

Khi đó F(i,x) là giá trị lớn nhứt của 3 chọn lựa:
* F(i-1, x + 1 - T_thang_máy/T_lửa) nếu (x + 1 - T_thang_máy/T_lửa >= 0: mình có đủ thời gian đi xuống tầng ngay dưới; nhưng sẽ không ngừng lại)
* V[i-1) + F(i-1, x + 1 - T_thang_máy/T_lửa - T_ngừng/T_lửa) nếu (x + 1 - T_thang_máy/T_lửa - T_ngừng/T_lửa >= 0: mình có đủ thời gian đi xuống tầng ngay dưới và ngừng lại để vét tiền ở tầng này)
* -vô cùng (mình không đủ thời gian đi xuống tầng dưới)

Có quan hệ truy hồi ở trên rồi thì mình có thể cài đặt qui hoạch động => O(N*M) thay vì O(N^2) nếu vét cạn

(có gì sai sót mong được góp ý, xin cám ơn)

-thân