维修栅栏(动态规划练习) 解题日志

维修栅栏

输入文件:fence.in

输出文件:fence.out

问题描述:

小z最近当上了农场主!不过,还没有来得及庆祝,一件棘手的问题就摆在了小z的面前。农场的栅栏,由于年久失修,出现了多处破损。栅栏是由n块木板组成的,每块木板可能已经损坏也可能没有损坏。小z知道,维修连续m个木板(这m个木板不一定都是损坏的)的费用是sqrt(m)。可是,怎样设计方案才能使总费用最低呢?小z想请你帮帮忙。

输入格式:

输入文件的第一行包含一个整数n,表示栅栏的长度。

第二行包含n个由空格分开的整数(长整型范围内)。如果第i个数字是0,则表示第i块木板已经损坏,否则表示没有损坏。

 

输出格式:

输出文件中仅包含一个实数,表示最小维修费用。

注意:答案精确到小数点后3位。

数据规模:

    30%的数据中,n<=20。

    100%的数据中,n<=2500。

输入输出样例:

输入 输出
9

0 –1 0 1 2 3 0 –2 0

3.000

 

 【思路剖析】

f[i]表示第i个点时所付出的最小代价

f[i]=f[i-1]+1 or f[j-1]+√(i-j+1)

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注