Hướng dẫn giải của [TS10 Quảng Ninh 2025 - 2026] Dãy con tăng
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.
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ưởng
Dãy con không giảm chỉ có dạng một số lượng ~0~ rồi đến một số lượng ~1~. Giả sử chọn đúng ~z~ số ~0~ chung. Khi đó vị trí sau số ~0~ thứ ~z~ trong mỗi dãy là điểm bắt đầu chọn số ~1~. Số ~1~ có thể chọn thêm là min giữa số lượng ~1~ còn lại ở hai dãy. Duyệt ~z~ từ ~0~ đến số ~0~ chung tối đa và lấy giá trị lớn nhất.
Độ phức tạp
~O(n+m)~.
Bình luận