Dãy con tăng dài nhất
Đề bài
Mô tả
Leon là một sinh viên chăm chỉ, thường dành thời gian rảnh để suy ngẫm về các dãy số nguyên. Hôm nay, cậu đặc biệt quan tâm đến các dãy tăng.
Một dãy con được tạo thành bằng cách xóa không hoặc nhiều phần tử khỏi một dãy và giữ nguyên thứ tự các phần tử còn lại. Dãy con tăng dài nhất của một dãy là dãy con dài nhất có các phần tử tăng ngặt. Dãy con này không nhất thiết duy nhất. Ví dụ, dãy con tăng dài nhất của dãy có thể là hoặc , cả hai đều có độ dài .
Leon đưa cho bạn bài toán sau:
Cho dãy , gọi là một dãy con của . Độ dài lớn nhất có thể của là bao nhiêu, sao cho độ dài dãy con tăng dài nhất của không vượt quá ?
Bài này quá dễ với bạn, nên Leon quyết định hỏi thêm. Cậu đưa cho bạn một dãy ban đầu gồm số nguyên, sau đó đặt câu hỏi. Bạn vẫn giải bài toán trên, nhưng dãy và số nguyên thay đổi theo từng câu hỏi: Leon cho trực tiếp số nguyên , và cho số nguyên , nghĩa là dãy gồm phần tử đầu tiên của dãy .
Với mỗi câu hỏi, hãy đưa ra đáp án của bài toán trên với dãy và số nguyên tương ứng.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , trong đó là số phần tử của dãy và là số câu hỏi (, ).
Dòng thứ hai chứa số nguyên là các phần tử của dãy ().
dòng tiếp theo, dòng thứ chứa hai số nguyên và : bạn phải giải bài toán trên với phần tử đầu tiên của và số nguyên ().
Dữ liệu ra
Với mỗi câu hỏi, in ra một dòng chứa đáp án.
Ràng buộc
- , .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 11 6 9 6 3 1 5 12 8 4 2 2 2 5 1 7 2 9 1 9 2 11 1 11 11 |
4 6 5 8 7 11 |
Câu 1: với chọn , dãy con tăng dài nhất của có độ dài . Câu 2: với chọn , độ dài . Câu 3: chọn . Câu 4: chọn . Câu 5: chọn . Câu 6: chọn cả dãy, dãy con tăng dài nhất có độ dài . |
| 6 6 3 3 1 2 2 4 2 1 4 1 5 1 5 2 6 1 6 2 |
2 3 4 5 4 5 |
Dãy tăng phải tăng ngặt nên hai số bằng nhau không tạo thành dãy tăng: câu 1 chọn , câu 3 chọn . Câu 6: với chọn hoặc , không thể chọn cả phần tử vì tăng. |
Bình luận