Chọn số không liền kề giá trị
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho dãy gồm $n$ số nguyên dương $a_1, a_2, \dots, a_n$. Trong mỗi bước, bạn có thể chọn một phần tử có giá trị $x$ đang có trong dãy, nhận được $x$ điểm, sau đó xóa bỏ phần tử đó cùng tất cả các phần tử có giá trị $x - 1$ và $x + 1$. Hãy tìm tổng điểm lớn nhất có thể đạt được.
Dữ liệu vào
- Dòng đầu chứa số nguyên $n$ ($1 \le n \le 10^5$).
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng điểm lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 9 1 2 1 3 2 2 2 2 3 |
10 |
Giới hạn
- $1 \le n \le 10^5, 1 \le a_i \le 10^5$
Community Discussion