Để thuận tiện hơn cho việc tính toán, ta có thể định nghĩa hàm \(F(i, j)\) là thời điểm gần nhất tính từ thời điểm \(j\) mà đèn tại đỉnh \(i\) bật xanh. Dễ thấy rằng chu kỳ sáng đèn tại đỉnh \(i\) là \(T_i = r_i + g_i\) nên ta có thể dựa vào \(T_i\) và \(c_i\) để tính \(F(i, j)\) trong \(O(1)\).

Subtask 1 (26% số điểm): k = 0.

Vì \(k = 0\) nên ta không cần phải quan tâm đến việc mua đủ các món đồ cần thiết, do đó thuật toán tối ưu cho \(subtask\) này là: Đi một mạch từ đỉnh \(1\) đến đỉnh \(n\), tại mỗi đỉnh thì ta sẽ đợi đến thời điểm gần nhất mà đèn tín hiệu tại đỉnh đó bật xanh để di chuyển sang đỉnh \(i + 1.\)

Độ phức tạp: \(O(n)\)

Subtask 2 (28% số điểm): k = 1.

Gọi \(dp(i, j)\) là thời điểm nhỏ nhất để đi đến đỉnh \(i\) và trạng thái mua là \(j (j = 0\) nếu chưa mua được món đồ cần thiết và \(j = 1\) nếu đã mua được). Ta có công thức:

\( \ \ \) \(dp(i, 0) = F (i − 1, dp(i − 1, 0)) + t_{i−1}.\)

\( \ \ \) \(dp(i, 1) = max(F (i − 1, dp(i − 1, 1)) + t_{i−1}, dp(i, 0) + p_i);\)

Từ đó suy ra kết quả bài toán.

Độ phức tạp: \(O(n)\)

Subtask 3 (46% số điểm): Không có ràng buộc gì thêm.

Vì số món đồ cần mua nhỏ nên tại đỉnh \(i\), ta sử dụng dãy bit để lưu trạng thái đã mua được chưa cho từng món đồ. Gọi \(dp(i, mask)\) là thời điểm nhỏ nhất để đi đến đỉnh \(i\) và trạng thái mua là mask. Kết hợp kỹ thuật quy hoạch động đẩy để tối ưu chi phí chuyển nhãn.

Độ phức tạp: \(O(n × 2k)\)