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.
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