題目描述

最近，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])²+min(f[i-1][k]+c*abs(k-j)),k<=maxh

這樣時間復雜度是O(nh²)，會超時，肯定要優化。

怎么優化呢？可以把絕對值拆開，于是狀態轉移方程變為

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

? ? ? ? ? (j-h[i])²+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])²+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; }

轉載于:https://www.cnblogs.com/GXZlegend/p/6306232.html

總結

以上是生活随笔為你收集整理的【bzoj1705】[Usaco2007 Nov]Telephone Wire 架设电话线 dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。