0%

维修栅栏

题目描述

农场的栅栏年久失修,出现了多处破损,晶晶准备维修它,栅栏是由 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;
}
  • 本文作者: rcxzsc
  • 本文链接: https://rcxzsc.com/archives/393/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY 许可协议。转载请注明出处!