Bệ phóng năng lượng
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ bệ đá xếp thành một hàng ngang đánh số từ $1$ đến $N$, bệ đá thứ $i$ có độ cao $H_i$. Ban đầu bạn đứng ở bệ đá $1$ và muốn di chuyển tới bệ đá $N$.
Từ bệ đá $i$, bạn có thể nhảy tới bệ đá $i+1$ hoặc $i+2$ (nếu không vượt quá $N$). Thông thường, chi phí nhảy từ bệ $i$ sang bệ $j$ là $|H_i - H_j|$. Tuy nhiên, một số bệ đá được trang bị bệ phóng: nếu bạn nhảy từ một bệ đá có bệ phóng, chi phí cho bước nhảy đó bằng $0$ (bất kể độ cao chênh lệch).
Tìm tổng chi phí nhỏ nhất để đi từ bệ $1$ đến bệ $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 $H_1, H_2, \dots, H_N$ ($1 \le H_i \le 10^9$).
- Dòng thứ ba chứa xâu nhị phân $S$ độ dài $N$, trong đó $S_i = 1$ nếu bệ đá $i$ có bệ phóng, ngược lại $S_i = 0$.
Dữ liệu ra
- Một số nguyên duy nhất là chi phí nhỏ nhất để đi từ $1$ đến $N$.
Ví dụ
| Input | Output |
|---|---|
| 5 10 30 40 20 50 01000 |
30 |
| 4 10 100 10 100 0000 |
90 |
Giới hạn
- $1 \le N \le 10^5$.
- $1 \le H_i \le 10^9$.
Community Discussion