Informatica Online Judge

  수줍은 Bad Hair Day [0989 / 03DD]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 13   Total Tried : 37


The Champion of this Problem (C++) : gst19076 - ms / 1917byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

기본적으로 Bad Hair Day문제는 잘 알고 있을 것이다.

이 문제의 목적은 소들의 머리스타일을 확인하는 수의 합을 구하는 것이다.

예를 들어

10 3 7 4 12 2 인 경우에는 머리 스타일을 확인할 수 있는 수는 5이다.

이 수 5를 10 3 7 4 12 2 의 Bad Hair Day 수라고 하자. 이 문제가 이해가 잘 안되면 200번 문항을 참고하기 바란다.

어떤 수열이 주어질 때, 이 수열의 Bad Hair Day 수는 정해진다.

이 수가 클수록 서로 많은 소들의 머리스타일을 확인할 수 있다.

오늘은 유난히 소들이 머리스타일이 마음에 들지 않는다. 따라서 최대한 머리 스타일을 들키기 싫어한다.

N마리의 소의 키가 주어질 때, a번째 소부터 b번째 소까지의 모든 소들을 뒤집으면 되면 Bad Hair Day수는 변한다.

이 문제의 목적은 Bad Hair Day 수를 최소화 하는 것이다. 주어진 소의 배치에서 한 번의 뒤집기로 얻을 수 있는 최소의 Bad Hair Day수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 소의 수를 나타내는 N이 입력된다.
다음 줄에 N마리의 소가 공백으로 구분되어 입력된다.

[입력값의 정의역]
2 <= N <= 1,000
1 <= a < b <= N
1 <= 소의 키 <= 1,000,000,000

[Sub Task Info]
#1 : N <= 100
#2 : N <= 500
#3, #4 : N <= 1,000

Output

주어진 조건에서 최소 Bad Hair Day 수를 출력한다.

IO Example

입력
3
3 2 1

출력
0

* 설명 : 1번 소부터 3번 소까지를 뒤집으면 1 2 3이 된다. 이 상태에서의 Bad Hair Day수는 0이다. 이 보다 더 적은 Bad Hair Day 수는 구할 수 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]