Bò nhảy Pogo

Lời giải: Bò nhảy Pogo

Hướng tiếp cận

Quy hoạch động $O(N^2)$ với tối ưu hóa bằng kỹ thuật hai con trỏ (two pointers) để duy trì giá trị max chạy.

Nhận xét quan trọng

1. Sắp xếp các mục tiêu theo vị trí. Ta xét riêng hai hướng: sang phải và sang trái.
2. Định nghĩa $DP[i][j]$ = điểm tối đa khi bò nhảy đến mục tiêu $i$ và bước nhảy trước đó là từ $j$ đến $i$ (với $j<i$ khi đi sang phải).
3. Chuyển tiếp: $DP[i][j]=p_i+{max}_{k\ge i,x_k-x_i\ge x_i-x_j}(DP[k][i])$.
4. Sử dụng running maximum và two pointers: khi $j$ giảm (khoảng cách $x_i-x_j$ tăng), con trỏ $k$ cũng giảm (ngưỡng khoảng cách tối thiểu tăng, nên ít mục tiêu hơn thỏa mãn), cho phép tính $O(1)$ mỗi trạng thái.

Thuật toán

1. Sắp xếp $N$ mục tiêu theo vị trí tăng dần.
2. Chạy DP cho hướng phải: duyệt $i$ từ $N-1$ về $0$, với mỗi $i$ duyệt $j$ từ $0$ đến $i-1$, duy trì con trỏ $k$ và giá trị max chạy.
3. Lặp lại cho hướng trái (đảo dấu tọa độ, reverse mảng).
4. Đáp án là giá trị lớn nhất tìm được.

Độ phức tạp

• Thời gian: $O(N^2)$
• Bộ nhớ: $O(N^2)$