Thành phố Cuồng loạn

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 ...

T1 link Đây là một bài toán khá đơn giản, có thể giải ngay bằng phương pháp quét đường, nhưng đáng tiếc là cách tiếp cận đó gây ra TLE, chỉ đạt được 80 điểm. Giải pháp thực sự lại đơn giản đến bất ngờ. Có thể giải bài này bằng cách duyệt từ cuối về đầu một vòng lặp 1e7, mỗi lần cộng thêm giá trị lớn nhất. code #include <bits/stdc++.h> usi ...