【USACO07NOV】电话线Telephone Wire

题目描述

电信公司要更换某个城市的网线。新网线架设在原有的 N(2 <= N <= 100,000)根电线杆上，第

i 根电线杆的高度为 height_i 米(1 <= height_i <= 100)。网线总是从一根电线杆的顶端被引到

相邻的那根的顶端，如果这两根电线杆的高度不同，那么电信公司就必须为此支付 C*电线

杆高度差(1 <= C <= 100)的费用。电线杆不能移动，只能在相邻电线杆间按原有的顺序架设

网线。加高某些电线杆能减少架设网线的总花费，但需要支付一定的费用，一根电线杆加高

X 米的费用是 X^2。请你计算一下，如何合理地进行这两种工作，使网线改造工程的最小费

用。

输入

Line 1: Two space-separated integers: N and C
Lines 2..N+1: Line i+1 contains a single integer: heighti

输出

Line 1: The minimum total amount of money that it will cost Farmer John to attach the new telephone wire.

样例输入

5 2 2 3 5 1 4

样例输出

题解：

定义F[i][j]为前i个中第i个选长度为j时的最小费用

易知 F[i][j]=max(F[i-1][k]+abs(k-j)*c+(j-h[i])).

然后就是复杂度达到了10^9

于是就是优化：

由玄学得：F[i-1][k]+abs(k-j)*c+(j-h[i])是个二次函数然后有一个取最值的地方

我们只需找到这个地方就可以O(1)的转移了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=100005,INF=1999999999;
 7 int gi(){
 8     int str=0;char ch=getchar();
 9     while(ch>'9' || ch<'0')ch=getchar();
10     while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar();
11     return str;
12 }
13 int n,c,x[N],mh=0;
14 int F[N][105];
15 int main()
16 {
17     //freopen("tt.in","r",stdin);
18     n=gi();c=gi();
19     for(int i=1;i<=n;i++){x[i]=gi();if(x[i]>mh)mh=x[i];} 
20     memset(F,127/3,sizeof(F));
21     for(int i=x[1];i<=mh;i++)F[1][i]=(i-x[1])*(i-x[1]);
22     int tp=0,ft,tmp,bt;
23     for(int i=2;i<=n;i++)
24     {
25         bt=x[i-1];
26         for(int k=x[i];k<=mh;k++)
27         {
28             tp=(k-x[i])*(k-x[i]);
29             ft=INF;
30             for(int j=bt;j<=mh;j++)
31             {
32                 tmp=F[i-1][j]+abs(k-j)*c+tp;
33                 if(tmp<F[i][k])
34                 {
35                     F[i][k]=tmp;
36                     bt=j;
37                 }
38                 if(tmp>ft)break;
39                 ft=tmp;
40             }
41         }
42     }
43     int ans=INF;
44     for(int i=x[n];i<=mh;i++)if(F[n][i]<ans)ans=F[n][i];
45     cout<<ans;
46     return 0;
47 }