Chọn Nhà Không Kề Nhau Trên Vòng Tròn
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ ngôi nhà xếp thành một vòng tròn theo thứ tự $1, 2, \dots, N$ (trong đó nhà $1$ và nhà $N$ cũng nằm kề nhau). Ngôi nhà thứ $i$ có giá trị tài sản là $a_i$.
Hãy chọn một tập hợp các ngôi nhà sao cho không có hai ngôi nhà nào được chọn nằm kề nhau trên vòng tròn và tổng giá trị của các ngôi nhà được chọn là lớn nhất.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $N$ ($1 \le N \le 2 \cdot 10^5$).
- Dòng thứ hai chứa $N$ số nguyên không âm $a_1, a_2, \dots, a_N$ ($0 \le a_i \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng giá trị lớn nhất có thể đạt được.
Ví dụ
| Input | Output |
|---|---|
| 4 2 3 2 1 |
4 |
Giới hạn
- $1 \le N \le 2 \cdot 10^5$
- $0 \le a_i \le 10^9$
Community Discussion