1209번 - 단조수열 만들기
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 137 | 65 | 42 | 41.584% |
문제
음이 아닌 정수로 이루어진 수열 A1, A2, …, AN이 있다. 단조수열 B1, B2, …, BN을 만들어서 |A1-B1| + |A2-B2| + … + |AN-BN|을 최소로 하는 프로그램을 작성하시오.
단조수열이란 B1≤B2≤…≤BN을 만족하거나 B1≥B2≥…≥BN를 만족하는 수열을 말한다.
입력
첫째 줄에 수열의 길이 N이 주어진다. (1≤N≤2,000) 이어서 둘째 줄부터 N개의 줄에 걸쳐 A1, A2, …, AN이 순서대로 주어진다. (0≤Ai≤1,000,000,000)
출력
첫째 줄에 절대값의 합의 최소값을 출력한다.
예제 입력
7 1 3 2 4 5 3 9
예제 출력
3
힌트
출처
Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO February 2008 Contest > Gold 1번
- 문제를 만든 사람: author5