Dãy con dài nhất
Đề bài
Mô tả
Cho một hoán vị gồm số từ đến là và cặp chỉ số với . Bạn có thể thực hiện một loạt các bước dựa trên các cặp này. Ở mỗi bước, bạn chọn một cặp và đổi chỗ hai số ở vị trí và trong hoán vị . Mỗi cặp có thể được dùng bao nhiêu lần tùy ý.
Một dãy con tăng độ dài của là
Gọi là độ dài dãy con tăng dài nhất của .
Nhiệm vụ của bạn là thực hiện các bước đổi chỗ để thu được hoán vị có lớn nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và .
- Dòng thứ hai chứa hoán vị .
- Mỗi dòng trong dòng tiếp theo chứa hai số nguyên , .
Dữ liệu ra
In ra một số nguyên duy nhất là giá trị lớn nhất của .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 2 5 2 4 6 3 1 5 6 1 5 |
4 | Thực hiện hai bước và để được hoán vị , có dãy con tăng độ dài . |
| 7 3 6 2 3 1 5 7 4 1 3 2 5 6 7 |
4 | Ví dụ bổ sung (không có trong đề gốc). Có thể đạt hoán vị với dãy con tăng . Lưu ý rằng xếp tăng dần các giá trị trong mỗi nhóm vị trí đổi chỗ được cho nhau, tức , chỉ cho độ dài . |
Bình luận