Tên Trộm Thông Minh

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved