Tóm tắt đề bài

Có một chiếc xe điện với dung lượng pin là ~P~ đơn vị. Để di chuyển ~1~ ~km~ tốn ~1~ đơn vị pin. Xe hết pin sẽ không thể di chuyển. Có ~N~ trạm sạc pin cho xe nằm tại các vị trí ~a_1, a_2, ..., a_N~. Mỗi lần sạc thì pin sẽ về dung lượng tối đa là ~P~ đơn vị. Bạn sẽ bắt đầu ở vị trí ~0~ ~km~ với quả pin đầy. Hãy tìm cách di chuyển đến vị trí ~D~ mà sạc ít lần nhất.

Giới hạn: ~N \le 1000~, ~P, D \le 10^9~, ~a_i < D~.

Lời giải

• Để tiện xử lý, ta sẽ sắp xếp các trạm sạc theo thứ tự tăng dần. Đồng thời, ta coi như ~a_0 = 0~ vì ở vị trí ~0~ pin đã đầy, nên ta coi vị trí ~0~ cũng có trạm sạc.
• Ta sẽ quy hoạch động: gọi ~dp[i]~ là số lần sạc pin tối thiểu, khi ta có đầy pin ở vị trí ~a_i~, và ta có sạc ở trạm ~a_i~.
• Để có thể đến trạm ~a_i~ thì ta sẽ phải đầy pin ở một trạm ~a_j~ với ~j < i~ nào đó, mà ~a_i - a_j \le P~.
• Vì vậy, ban đầu ~dp[i] = \inf~, chỉ có ~dp[0] = 0~. Ta có công thức truy hồi: ~dp[i] = min (dp[j] + 1)~ với ~0 \le j < i~ và ~a_i - a_j \le P~.
• Kết quả sẽ là ~min~ của các ~dp[i]~ thỏa mãn ~D - a[i] \le P~ để ta có đủ điện. Cần lưu ý trường hợp không cần sạc lần nào, đó là khi ~D \le P~.

Độ phức tạp: ~O~ ~(N^2)~.