Tên Trộm Thông Minh
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Trên một con phố có $N$ ngôi nhà xếp thành một hàng ngang. Ngôi nhà thứ $i$ có số tiền là $a_i$. Hệ thống báo động sẽ kích hoạt nếu hai ngôi nhà kề nhau cùng bị trộm trong một đêm. Hãy tìm tổng số tiền lớn nhất có thể lấy được mà không kích hoạt báo động.
Cấu trúc con tối ưu: $dp[i] = \max(dp[i-1], dp[i-2] + a_i)$.
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, a_2, \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 có thể lấy được.
Ví dụ
| Input | Output |
|---|---|
| 4\n1 2 3 1 | 4 |
| 5\n2 7 9 3 1 | 12 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le a_i \le 10^9$
Community Discussion