#159. Con Ếch (FROG1)

Có tảng đá, được đánh số . Với mỗi (), tảng đá có chiều cao là . Một con ếch ban đầu ở tảng đá . Nó sẽ lặp lại hành động sau một số lần để đến được tảng đá : Nếu con ếch hiện đang ở trên đá , nó có thể nhảy đến đá hoặc đá . Chi phí phát sinh khi nhảy từ đá sang đá là .

Yêu cầu: Tìm tổng chi phí tối thiểu có thể để đến được tảng đá .

Dữ liệu:

• Dòng đầu tiên chứa số nguyên .
• Dòng thứ hai chứa số nguyên .

Kết quả: In ra chi phí tối thiểu.

Ví dụ:

Dữ liệu:

4
10 30 40 20

Kết quả:

30

Giải thích: Một đường đi tối ưu là .

• Chi phí từ là .
• Chi phí từ là . Tổng chi phí là .

Giới hạn: