J16 实践-3 栅栏维修

题目描述

农场的栅栏年久失修，出现了多处破损，佩奇准备维修它，栅栏是由 $n$ 块木板组成的，每块木板可能已经损坏也可能没有损坏。 佩奇知道，维修连续 $m$ 个木板（这 $m$ 个木板不一定都是损坏的）的费用是 $sqrt( m)$ 。可是，怎样设计方案才能使总费用最低呢？请你写程序帮忙计算。

输入格式

第一行包含一个整数 $n$，表示栅栏的长度。 第二行包含 $n$ 个由空格分开的整数 $A_i$，如果第 $i$ 个数是 $0$ ，则表示第 $i$ 块木板已经损坏，否则表示没损坏。

输出格式

一个实数，表示最小维修费用（注意：答案精确到小数点后 $3$ 位）。

样例输入

9
0 -1 0 1 2 3 0 -2 0

样例输出

3.000

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据： $1 \leq n \leq 2500 ; -1000 \leq A_i \leq 1000$ 。