Editorial for Bedao Regular Contest 07 - LIS


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

Ta nhận thấy, tổng độ dài của các dãy con tăng ngặt dài nhất kết thúc tại ~i~ đạt được khi dãy đó được sắp xếp tăng dần. Vì vậy, ta có cách làm như sau:

  • Sắp xếp mảng tăng dần.
  • Duyệt từ ~1~ đến ~n~, với mỗi ~i~ ta cộng thêm vào kết quả tích của số lần xuất hiện của phần tử thứ ~i~ với số phần tử khác nhau từ ~1~ đến ~i~.

Lưu ý: Với mỗi phần tử khác nhau chỉ cộng một lần.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.