[USACO07NOV]电话线Telephone Wire

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[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 Cios

  • 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根电线杆第i根高度为j是的最小费用ide

f[i][j]=min(f[i-1][k]+c*abs(k-j))+(j-h[i])^2函数

决策单调性:假设f[i][j-1]在k1时取最优,f[i][j]在k2时取最优,k2>=k1spa

可用go变量记录f[i][j-1]取最优值的位置,计算f[i][j]时从go开始枚举 ci

 

令函数p(k)=(f[i-1][k]+c*abs(k-j))string

p(k)是一个凹函数(随着k递增,p(k)先降低,后迅速上升)或者是单调递增函数 it

当p(k+1)>p(k)时,直接break,后面不存在更优的解 io

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int n,c,maxh,h[100001],f[100001][101],go;
 7 int main()
 8 {int i,j,l;
 9 //freopen("file.in","r",stdin);
10     cin>>n>>c;
11      for (i=1;i<=n;i++)
12      {
13         scanf("%d",&h[i]);
14       maxh=max(maxh,h[i]);
15      }
16      memset(f,127/3,sizeof(f));
17      for (i=h[1];i<=maxh;i++)
18      f[1][i]=(h[1]-i)*(h[1]-i);
19       for (i=2;i<=n;i++)
20       {
21         go=h[i-1];
22          for (j=h[i];j<=maxh;j++)
23          {
24             int tmp=(j-h[i])*(j-h[i]);
25              int pre=2e9;
26              for (l=go;l<=maxh;l++)
27              {
28                 int tmpp=f[i-1][l]+c*abs(j-l)+tmp;
29                 if (tmpp<f[i][j])
30                 {
31                     f[i][j]=tmpp;
32                     go=l;
33                 }
34                  if (tmpp<pre) pre=tmpp;
35                  else
36                   break;
37              }
38          }
39       }
40       int ans=2e9;
41     for (i=h[n];i<=maxh;i++)
42      ans=min(ans,f[n][i]);
43     cout<<ans;
44 }