Khu Phố Vòng Tròn

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
48
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Có $N$ ngôi nhà xếp thành một vòng tròn khép kín (ngôi nhà thứ $1$ nằm kề với ngôi nhà thứ $N$). Ngôi nhà thứ $i$ chứa số tiền $a_i$. Không thể trộm hai ngôi nhà nằm kề nhau trên vòng tròn.

Hãy tìm tổng số tiền lớn nhất có thể lấy được.

Cấu trúc con tối ưu: tách bài toán vòng tròn thành 2 bài toán tuyến tính: xét đoạn $[1..N-1]$ (bỏ nhà cuối) và đoạn $[2..N]$ (bỏ nhà đầu), rồi lấy giá trị lớn hơn.

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 không âm $a_1, \dots, a_N$ ($0 \le a_i \le 10^9$).
Dữ liệu ra
  • In ra tổng số tiền lớn nhất.
Ví dụ
Input Output
3\n2 3 2 3
4\n1 2 3 1 4
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le a_i \le 10^9$
Draft saved