Hướng dẫn giải của Bò nhảy Pogo

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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

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.
Định nghĩa $D P [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).
Chuyển tiếp: $D P [i] [j] = p_{i} + {max}_{k \geq i, x_{k} - x_{i} \geq x_{i} - x_{j}} (D P [k] [i])$ .
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

Sắp xếp $N$ mục tiêu theo vị trí tăng dần.
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.
Lặp lại cho hướng trái (đảo dấu tọa độ, reverse mảng).
Đá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})$

Bình luận

Không có bình luận tại thời điểm này.