Editorial for Bedao Regular Contest 05 - CARRAY


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

DP, LIS.

Ý tưởng
  • Với từng ~a[i]~, giả sử ta chọn ~a[i]~ làm phần tử đầu tiên được thêm để tạo thành dãy B, ta rút ra nhận xét như sau:

  • Các phần tử được thêm vào dãy ~B~ bằng cách thêm vào đầu, ta thêm lần lượt và vẫn giữ nguyên trình tự khi nằm trên dãy ~A~. Nhận ra rằng các phần tử đó tạo ra dãy con giảm dài nhất có phần tử đầu tiên là ~a[i]~ . Vì là dãy giảm dài nhất nên khi ta thêm lần lượt vào dãy ~B~ bằng cách thêm vào đầu thì dãy B vẫn tăng dần (thỏa mãn tính chất, và các số được thêm vào luôn tăng, dài nhất).

  • Tương tự với các phần tử được thêm vào dãy ~B~ Bằng cách thêm vào đuôi. Nhận ra rằng các phần tử đó tạo ra dãy con tăng dài nhất có phần tử đầu tiên là ~a[i]~ .

--> Với từng ~a[i]~ ta chỉ cần tìm các dãy tăng hoặc giảm ngặt bắt đầu bằng ~a[i]~ và kết quả là giá trị lớn nhất giữa tổng hai độ dài trừ đi ~1~ vì ~a[i]~ lặp lại hai lần.

Đọc thêm về cách tìm LIS trong ~O(nlogn)~ tại đây


Comments

Please read the guidelines before commenting.


There are no comments at the moment.