구간 덧셈

시간 제한4초메모리 제한2048 MB

요약

길이 n(23 이하)인 배열에서 연속 구간에 실수를 더하는 연산으로 모든 원소를 0으로 만드는 최소 연산 횟수를 구합니다.

문제

배열 $a$ 에는 정수 $n$ 개가 들어 있다. 이 배열에 대해 연산을 수행할 수 있다. 한 번의 연산에서 임의의 실수 $x$ 를 $a$ 의 연속된 구간에 더할 수 있다.

$a$ 의 모든 원소를 $0$ 으로 만들기 위해 수행해야 하는 연산 횟수의 최솟값을 구하라.

첫 줄에 정수 $n$ ( $1 \leq n \leq 23$ )이 주어진다.

둘째 줄에 배열 $a_1, a_2, \ldots, a_n$ ( $0 \leq a_i \leq 10^9$ )이 주어진다.

필요한 연산 횟수의 최솟값을 나타내는 정수 하나를 한 줄에 출력한다.