Hướng dẫn giải của Dây thừng và hàng rào

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: Dây thừng và hàng rào

Hướng tiếp cận

Với $N \leq 10$ cọc, duyệt brute-force tất cả $2^{N}$ tập con cọc cần xóa. Với mỗi tập con còn lại, kiểm tra bò có thể thoát không bằng thuật toán stack triệt tiêu chuỗi.

Nhận xét quan trọng

Tất cả cọc nằm tại cùng tọa độ $x$ . Chỉ các giao điểm của dây với đường thẳng $x = x_{c ọ c}$ có ý nghĩa.
Mỗi giao điểm tại độ cao $y_{c}$ được gán nhãn là cọc có $y$ lớn nhất mà vẫn nhỏ hơn $y_{c}$ (trong các cọc còn lại).
Dùng stack: nếu đỉnh stack cùng nhãn và ngược chiều với giao điểm hiện tại → triệt tiêu (pop); ngược lại → push.
Stack rỗng sau khi xử lý hết ↔ bò có thể thoát.

Thuật toán

Tiền xử lý: tính tất cả giao điểm của dây với hàng rào (toàn bộ, không phụ thuộc tập con cọc).
Với mỗi mask (tập con bỏ cọc):
- Lọc giao điểm: chỉ giữ những giao điểm có cọc bên dưới (trong tập cọc còn lại).
- Chạy thuật toán stack.
- Nếu stack rỗng → cập nhật đáp án.

Độ phức tạp

Thời gian: $O (2^{N} \cdot M)$
Bộ nhớ: $O (M)$

Bình luận

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