실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 1024 MB |
그루의 나무가 까지 번호가 매겨져 있는 직선형 화단에 심어져 있습니다. 나무 는 각각 화단의 부터 까지 범위의 구역을 차지하며 나무들이 차지하는 구역은 겹치지 않습니다. 나무 는 만큼의 온도를 낮춰야 최적의 조건으로 성장하기 때문에 최적의 온도를 만들수 있는 에어컨을 설치하려고 합니다.
화단에는 에어컨 대가 설치되어 있으며 번째 에어컨은 부터 까지 범위의 구역을 ()만큼 냉각시킬 수 있고 만큼의 요금이 듭니다. 에어컨이 냉방하는 구역은 겹칠 수 있습니다.
모든 나무들의 냉방 조건을 만족시킬 수 있는 최소 금액을 구해주세요
입출력 예시
그루의 나무와 대의 에어컨이 존재합니다.
먼저 그루의 나무의 정보가 나옵니다. ()
모든 나무의 냉방 조건을 만족 시키며 에어컨를 가동하는 최소 금액을 나타내는 단일 정수
2 4 1 5 2 7 9 3 2 9 2 3 1 6 2 8 1 2 4 2 6 9 1 5
10
최소한의 돈을 들이는 한 가지 가능한 방법 구역 , , 그리고 를 냉방하는 경우며, 이 경우 비용은 이 됩니다.
출처: USACO 2023 January Contest, Bronze Problem 2. Air Cownditioning II