COCI 2017/2018 Contest #4- 산 깎기 > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


4936 : 산 깎기

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
11 회   
시도횟수
68 회   

문제

정올시에서는 정올시 외곽의 산을 관광지로 개발하려는 계획을 추진 중이다.

시에서는 산을 길게 일자로 N개의 구간으로 나누어서 각 구간의 높이를 측량했다.

정올시는 산을 '뾰족한 모양'으로 다듬으면 관광객을 유치할 수 있을 것으로 보고 있다.

 

여기서 뾰족한 모양이란 산의 높이 조건이 다음을 만족하는 경우를 말한다.

 

- i번째 구간의 높이가 a_i라고 하면 위치 t를 하나의 꼭대기로 정해서 모든 1<=i<=N에 대해 a_i = a_t - |t - i|가 되도록 할 수 있다.

- 모든 구간의 높이가 1 이상이다.

 

시에서는 1의 비용을 들여 한 구간의 높이를 1만큼 높이거나 깎을 수 있다.

뾰족한 산을 만들기 위한 최소 비용을 계산하자.


입력형식

첫 줄에 N (1 <= N <= 100000)이 주어진다.

둘째 줄에 각 구간의 높이가 일렬로 주어진다. 높이는 1에서 10^9사이의 정수이다.


출력형식

뾰족한 모양의 산을 만들기 위한 최소 비용을 출력하라.


입력 예

복사하기

4
1 1 2 3

출력 예

복사하기

3

입력 예

복사하기

5
4 5 7 2 2

출력 예

복사하기

4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP