Thành phố Cuồng loạn

Tối ưu hóa bài toán chuyển trạng thái với Bitmask DP và BFS Trong các bài toán yêu cầu tìm số bước tối thiểu để chuyển đổi giữa các trạng thái, Quy hoạch động trạng thái (Bitmask DP) thường được nghĩ đến đầu tiên. Tuy nhiên, nếu trạng thái mới (nmask) có thể lớn hơn trạng thái hiện tại (mask), việc cập nhật DP theo thứ tự thông thường sẽ gặp lỗ ...

Khi giải các bài toán quy hoạch động trong sách Thông tin học Olympic, ta cần áp dụng linh hoạt các kỹ thuật như DP số học, DP trạng thái nén, DP trên cây, DP theo khoảng và tối ưu bằng hàng đợi đơn điệu. Dưới đây là phân tích và mã nguồn minh họa cho từng dạng. DP Số học (Digit DP) Đây là kỹ thuật đếm số thỏa mãn điều kiện dựa trên từng chữ s ...