[四连测(一)]电话线路

题目描述

最近,约翰的奶牛们越来越不满足于牛棚里一塌糊涂的电话服务,于是,她们要求
约翰把那些老旧的电话线换成性能更好的新电话线。新的电话线架设在己有的n根
电话线杆上,第i根电话线的高度为hi, ( 1 <= hi<= 100)。电话线总是从一根电话
线杆的顶端被弓}到相邻的那根的顶端,如果这两根电话线杆的高度hi和hj不同,那
么约翰就必须支付c * |hi - hj|的费用,当然,你不能移动电话线杆,只能按照原有
的顺序在相邻杆间架设电话线。
加高某些电话线杆能减少架设电话线的总费用,尽管这项工作也需要支付一定的
费用。更准确的说,如果他把一根电话线杆加高x米的话,他需要付出x^2费用。
请你帮约翰计算一下,如果合理的进行这两项工作,他最少要在这个电话线改造
工程中花多少钱

输入

第一行输入两个数n和c, 含义如上
接下来n行,每行一个整数hi

输出

输出约翰完成电话线改造工程需要花费的最小费用

样例输入

5 2
2
3
5
1
4

样例输出

15

数据范围

N <= 100000,  C <= 100,  Hi < 100,答案不超过maxlongint。

解题思路

首先,确定题型:DP(感觉好难啊,看到DP就怕了)既然是DP,那该怎么定义呢?首先,第一维i肯定是第几根电线杆。这是毋庸置疑的,那么第二维呢?这里有几个选择。

(一)第二维放第i根电线子改变后的高度。

(二)第二维放第i根电线子所增加的高度。

此题想来只能用二维DP,这样的数据范围三维是绝对会爆的,于是我们就不考虑三维这样的情况。(然而考试时候深陷其中无法自拔,简单的二维都想不到了。。。。)

由于知道每根电线杆的原高度,我们用j表示新的高度(即第二维放第i根电线杆的高度)。那么便可以求出从a[i]到j所需要的费用,这样是比较好算的,并且保存了第i根电线杆j高时的最优状态,后面算高度差时也比较好用。

这样DP[i][j]就表示第i杆电线杆高度为j时所花的最小费用。

状态转移方程:dp[i][j]=minleft {dp[i-1][k]+c*left |j-k 
ight | 
ight }+left ( j - a[i] 
ight ) ^2

然而。。。其中有三个变量i,j,k。还不是用三重循坏不也爆了?这个时候,就要开始进行优化了。我们从状态转移方程中入手,min后面的那一块是一个定值,我们可以不用管。|j-k|一看就要分类讨论,于是分成了j <= k j > k。等于无论分在哪边效果一样的

于是,c * |j - k|就可以化了于是又得到两种不同情况的状态转移方程

dp[i][j] = minleft {dp[i - 1][k] + c * k 
ight } - c * j + (j - a[i])^{2}(k>=j)

dp[i][j] = minleft {dp[i - 1][k] - c * k 
ight } + c * j + (j - a[i])^{2}(k<j)

我们可以知道j其实在枚举更值得时候是一个定值,我们于是就可以将它提出来。做到简化的目的,你也许会想,这样依旧还是要爆。这时候我们最好就是要同时将j,k都枚举了。这样才能够不超时。事实上这是可以做到的。我们通过优化枚举j就可以达到效果

进行预处理,第一个电线杆达到的j高度的花费就是(j - a[i])^2

首先就要确定枚举的方向,可以清楚的是,这两个分类讨论的情况是需要分开进行处理的。那么第一个(k>=j,意思是如果k只能取j到100的值)就需要倒着进行枚举。因为这样就可储存中间的min,同理,第二个(k<j)正着枚举。

我们用两个变量,在枚举过程中,储存最小值,更新DP值。更新完之后也储存这一个情况的最小值。可能有点抽象。具体看一下代码

for (int i = 2;i <= n; i++){//枚举每一个电线杆,第一个电线杆进行了预处理
        int minn = inf ,minn1 = inf;
        for (int j = 1 ;j <= a[i] ;j ++ ){//这一段是k<j的情况,由于j是不可能取到小于a[i]的值,因此这里就是求一个最小值
            minn = min((dp[i - 1][j] - c * j) , minn);
        }
        for (int j = a[i] ; j <= 100 ; j ++ ){//k<j的情况,在这里我们就需要更新DP的值
            minn = min(minn,dp[i - 1][j] - c * j);
            dp[i][j] = min(dp[i][j],minn + c * j + (j - a[i]) * (j - a[i]));
        }
        for (int j = 100;j >= a[i]; j -- ){//k > j的情况,在这里我们需用另一个变量,保存最小值。并且更新DP的值。
            minn1 = min(minn1, (dp[i - 1][j] + c * j));
            dp[i][j] = min(dp[i][j],minn1 - c * j + (j - a[i]) * (j - a[i]));
        }
    }

完整代码就不放了,其实除了输入输出与预处理,就这一部分代码了。

总结

DP总觉得还是比较难想啊。考试时候根本不好弄DP,纵使我想出了DP,也还是想不到优化的方法。此题的关键点可以说不在DP,而在优化。对于DP枚举j顺序的改变可以说很难想了。但实现却是不难,想到一种简单的状态转移方程就显得尤其重要,回想了一下,在我想状态转移方程的时候,基本上都转移不了,根本无法表示,更不用说做题了,这就需要我去抓住题目中的本质信息就比如说这道题,题目中编号肯定是有的,同时高度又决定了值,所以我们最好将高度定下来,于是高度变成了j来进行枚举。而优化的步骤则抓住了不同DP状态的条件,改变顺序。有些题,拿到题还是要判断算法,用那样的一种思路去进行计算。

原文地址:https://www.cnblogs.com/lover-fucker/p/13566702.html