Bài 3. Chi phí
Cho dãy số nguyên a1, a2, . . ., an (0 ≤ ai ≤ 109, 1 ≤ n ≤ 106). Với dãy số nguyên này ta có thể thực hiện phép xử lý Reduce(i) thay thế 2 phần tử ai và ai+1 bằng max{ai, ai+1} với chi phí là max{ai, ai+1}.
Sau n-1 lần thực hiện phép xử lý trên, ta được dãy số độ dài 1. Chi phí biến đổi dãy được tính bằng tổng chi phí của tất cả các phép xử lý đã thực hiện.
Yêu cầu: Cho n và các số ai. Hãy xác định chi phí nhỏ nhất đưa dãy về độ dài bằng 1.
Dữ liệu: Gồm n+1 dòng:
· Dòng đầu tiên chứa số nguyên n,
· Dòng thứ i trong n dòng tiếp theo chứa số nguyên ai.
Kết quả: In ra một số nguyên – chi phí biến đổi tìm được.
Ví dụ:
|
input |
output |
|
3 1 2 3 |
8 |
đề thi khảo sát hsg trường thôi mà mn