[USACO07NOV]电话线Telephone Wire

时间限制: 1 Sec  内存限制: 128 MB

题目描述

电信公司要更换某个城市的网线。新网线架设在原有的 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

样例输出

15

题解：

f[i][j]表示第i个电线杆高度为j时所需要的最少的费用。

然后很快就可以得出暴力代码，每次枚举上一个电线杆的高度就可以了。

先付上暴力代码：（TLE到爆表）

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 using namespace std;12 long long n,m;13 long long a[100001],f[100001][101],mmax;14 int main()15 {16 long long i,j,k;17 scanf("%lld%lld",&n,&m);18 memset(f,127/3,sizeof(f));19 for(i=1;i<=n;i++)20 {21 scanf("%lld",&a[i]);22 mmax=max(mmax,a[i]);23 }24 for(i=a[1];i<=mmax;i++)25 {26 int s=i-a[1];27 f[1][i]=s*s;28 }29 for(i=1;i<=n;i++)30 {31 for(j=a[i-1];j<=mmax;j++)32 {33 for(k=a[i];k<=mmax;k++)34 {35 int s=k-a[i];36 f[i][k]=min(f[i][k],s*s+f[i-1][j]+m*abs(j-k));37 }38 }39 }40 long long ans=2000000000000000000;41 for(i=a[n];i<=mmax;i++)42 ans=min(ans,f[n][i]);43 cout<
               
              
             
            
           
          
         
        
       
      

显然是需要优化的，仔细想一想就可以看出，每次实际上只有两种情况：

1.i-1的高度比i低。

2.i-1的高度比i高。

第一种情况下f[i][j]的结果为f[i-1][min]+abs(j-min)*k+(j-a[i])^2显然是有最小值的，所以只要记录min就可以直接算出f[i][j]的值。

第二种情况下f[i][j]的结果为f[i-1][min]+abs(j-min)*k+(j-a[i])^2，但由于随着j的增加每次min的值都有可能会改变，所以需要用到一个单调队列来记录最小值。

以下为AC代码：

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 using namespace std;12 long long n,m;13 long long a[100001],f[100001][101],mmax;14 int main()15 {16 long long i,j,k;17 scanf("%lld%lld",&n,&m);18 memset(f,127,sizeof(f));19 for(i=1; i<=n; i++)20 {21 scanf("%lld",&a[i]);22 mmax=max(mmax,a[i]);23 }24 for(i=a[1]; i<=mmax; i++)25 {26 int s=i-a[1];27 f[1][i]=s*s;28 }29 for(i=2; i<=n; i++)30 {31 int p[101],head=1,tail=0,mmin=0;32 for(j=a[i-1];j
                
                 f[i-1][j])mmin=j;49 if(p[head]==j)head++;50 }51 }52 long long ans=1e18;53 for(i=a[n]; i<=mmax; i++)54 ans=min(ans,f[n][i]);55 cout<