题目描述
农场的栅栏年久失修, 出现了多处破损, 晶晶准备维修它, 栅栏是由 n 块木板组成的, 每块木板可能已经损坏也可能没有损坏. 晶晶知道, 维修连续 m 个木板 (这 m 个木板不一定都是损坏的) 的费用是 sqrt(m). 可是, 怎样设计方案才能使总费用最低? 请你也来帮帮忙.
输入格式
第一行包含一个整数 n(n≤2500), 表示栅栏的长度;
第二行包含 n 个由空格分开的整数(整型范围内). 如果第 i 个数字是 0, 则表示第 i 块木板已经损坏, 否则表示没有损坏.
输出格式
仅包含一个实数, 表示最小维修费用; 注意: 答案精确到小数点后 3 位.
输入样例
- 9
- 0 -1 0 1 2 3 0 -2 0
输出样例
3.000
题解
我们设 $dp[i][j]$ 表示修了第 $1$ 到第 $i$ 个栅栏且修了 $j$ 次 (段) 栅栏的最小值, 直接 dp 即可.
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- #define MAXN 2502
- using namespace std;
- int n;
- int a[MAXN];
- int s[MAXN];
- double dp[MAXN][MAXN];
- // 1: 有几个栅栏要修
- // 2: 有几次栅栏要修
- double ans = 2147483647, m = 2147483647;
- int main()
- {
- scanf("%d",&n);
- for( int i = 1, tmp = 0; i <= n; i++)
- {
- scanf("%d", &a[i]);
- if(!a[i]) s[++tmp] = i;
- }
- for( int i = 1; s[i]; i++)
- {
- for( int j = 1; j <= i; j++)
- {
- m = 2147483647;
- if(j == 1) m = sqrt(s[i] - s[j] + 1);
- else for( int k = j - 1; k < i; k++)
- m = min(m, dp[k][j - 1] + sqrt(s[i] - s[k + 1] + 1));
- dp[i][j] = m;
- if(!s[i + 1]) ans = min(ans, dp[i][j]);
- }
- }
- ans != 2147483647 ? printf("%0.3lf", ans) : puts("0.000");
- return 0;
- }
参考程序
来源: http://www.bubuko.com/infodetail-3045012.html