Problems
정올시에서는 정올시 외곽의 산을 관광지로 개발하려는 계획을 추진 중이다.
시에서는 산을 길게 일자로 N개의 구간으로 나누어서 각 구간의 높이를 측량했다.
정올시는 산을 '뾰족한 모양'으로 다듬으면 관광객을 유치할 수 있을 것으로 보고 있다.
여기서 뾰족한 모양이란 산의 높이 조건이 다음을 만족하는 경우를 말한다.
- i번째 구간의 높이가 a_i라고 하면 위치 t를 하나의 꼭대기로 정해서 모든 1<=i<=N에 대해 a_i = a_t - |t - i|가 되도록 할 수 있다.
- 모든 구간의 높이가 1 이상이다.
시에서는 1의 비용을 들여 한 구간의 높이를 1만큼 높이거나 깎을 수 있다.
뾰족한 산을 만들기 위한 최소 비용을 계산하자.
Input
첫 줄에 N (1 <= N <= 100000)이 주어진다.
둘째 줄에 각 구간의 높이가 일렬로 주어진다. 높이는 1에서 10^9사이의 정수이다.
Output
뾰족한 모양의 산을 만들기 위한 최소 비용을 출력하라.
Example #1
4
1 1 2 3
3
Example #2
5
4 5 7 2 2
4
Example #3
6
4 5 6 5 4 3
0
Source
COCI 2017/2018 Contest #4
You must sign in to write code.