维修栅栏

题目描述

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

输入格式

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

输出格式

仅包含一个实数,表示最小维修费用。注意:答案精确到小数点后 3 位

输入样例

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

输出样例

3.000

解题思路

很明显这是一道动态规划,我们设f[i]为前i个最小费用

那么,根据题目的意思,第i个栅栏可以选择与前面的栅栏一起修复,或者不和前面的栅栏一起,自己修自己,因此,我们分两种情况讨论,见代码

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
double f[2505];//前i个最小费用 
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		if (x == 0)
		{
			f[i] = f[i - 1] + 1;
			for (int j = 1; j < i; j++)
				f[i] = min(f[i], f[j-1] + sqrt(i - j + 1));
		}
		else
			f[i] = f[i - 1];
	}
	printf("%0.3lf\n", f[n]);
	return 0;
}