【bzoj1705】[Usaco2007 Nov]Telephone Wire 架设电话线 dp

时间:2021-11-26 00:39:16

题目描述

最近,Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务 于是,她们要求FJ把那些老旧的电话线换成性能更好的新电话线。 新的电话线架设在已有的N(2 <= N <= 100,000)根电话线杆上, 第i根电话线杆的高度为height_i米(1 <= height_i <= 100)。 电话线总是从一根电话线杆的顶端被引到相邻的那根的顶端 如果这两根电话线杆的高度不同,那么FJ就必须为此支付 C*电话线杆高度差(1 <= C <= 100)的费用。当然,你不能移动电话线杆, 只能按原有的顺序在相邻杆间架设电话线。Farmer John认为 加高某些电话线杆能减少架设电话线的总花费,尽管这项工作也需要支出一定的费用。 更准确地,如果他把一根电话线杆加高X米的话,他得为此付出X^2的费用。 请你帮Farmer John计算一下,如果合理地进行这两种工作,他最少要在这个电话线改造工程上花多少钱。

输入

第1行: 2个用空格隔开的整数:N和C

第2..N+1行: 第i+1行仅有一个整数:height_i

输出

第1行: 输出Farmer John完成电话线改造工程所需要的最小花费

样例输入

5 2
2
3
5
1
4

样例输出

15


题解

dp+优化

每个电线杆加高之后的最高高度肯定不超过高度最大值maxh,这是显然的。

首先有最基本的思路:

f[i][j]表示第i个柱子高度为j时的最小花费。

那么就有f[i][j]=(j-h[i])2+min(f[i-1][k]+c*abs(k-j)),k<=maxh

这样时间复杂度是O(nh2),会超时,肯定要优化。

怎么优化呢?可以把绝对值拆开,于是状态转移方程变为

f[i][j]=(j-h[i])2+min(f[i-1][k]-c*k)+c*j,k<=j

(j-h[i])2+min(f[i-1][k]+c*k)-c*j,k>=j

那么我们只要分别维护f[i-1][k]-c*k,k<=j和f[i-1][k]+c*k,k>=j的最小值即可,可以递推求出。

设min1[i][j]为k<=j时f[i][k]-c*k的最小值,min2[i][j]为k>=j时f[i][k]+c*k的最小值。

那么就有min1[i][j]=min(min1[i][j-1],f[i][j]-c*j)

min2[i][j]=min(min2[i][j+1],f[i][j]+c*j)

以及f[i][j]=(j-h[i])2+min(min1[i-1][j]+c*j,min2[i-1][j]-c*j)。

注意公式中有的是i有的是i-1,不要弄混。

于是时间复杂度被优化到了O(nh),解决了时间问题。

然而题目空间要求是64MB,这样开二维数组会MLE。

所以我使用了滚动数组黑科技,应该不难理解,注意细节。

听说少开一个二维数组好像也能过,没试过,反正滚动数组应该是最好的做法了吧。

还有柱子高度不能降低,所以注意一下循环起始点和终止点。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[102] , h[100002] , min1[102] , min2[102];
int main()
{
int n , c , m = 0 , i , j , ans = 0x3f3f3f3f;
scanf("%d%d" , &n , &c);
for(i = 1 ; i <= n ; i ++ )
scanf("%d" , &h[i]) , m = max(m , h[i]);
memset(f , 0x3f , sizeof(f));
for(i = h[1] ; i <= m ; i ++ )
f[i] = (i - h[1]) * (i - h[1]);
for(i = 2 ; i <= n ; i ++ )
{
memset(min1 , 0x3f , sizeof(min1));
memset(min2 , 0x3f , sizeof(min2));
for(j = h[i - 1] ; j <= m ; j ++ )
min1[j] = min(min1[j - 1] , f[j] - c * j);
for(j = m ; j >= 1 ; j -- )
min2[j] = min(min2[j + 1] , j >= h[i - 1] ? f[j] + c * j : 0x3f3f3f3f);
for(j = h[i] ; j <= m ; j ++ )
f[j] = (j - h[i]) * (j - h[i]) + min(min1[j] + c * j , min2[j] - c * j);
}
for(i = h[n] ; i <= m ; i ++ )
ans = min(ans , f[i]);
printf("%d\n" , ans);
return 0;
}