[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到爆表）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
using namespace std;
long long n,m;
long long a[],f[][],mmax;
int main()
{
long long i,j,k;
scanf("%lld%lld",&n,&m);
memset(f,/,sizeof(f));
for(i=;i<=n;i++)
{
scanf("%lld",&a[i]);
mmax=max(mmax,a[i]);
}
for(i=a[];i<=mmax;i++)
{
int s=i-a[];
f[][i]=s*s;
}
for(i=;i<=n;i++)
{
for(j=a[i-];j<=mmax;j++)
{
for(k=a[i];k<=mmax;k++)
{
int s=k-a[i];
f[i][k]=min(f[i][k],s*s+f[i-][j]+m*abs(j-k));
}
}
}
long long ans=;
for(i=a[n];i<=mmax;i++)
ans=min(ans,f[n][i]);
cout<<ans;
return ;
}
显然是需要优化的，仔细想一想就可以看出，每次实际上只有两种情况：
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代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
using namespace std;
long long n,m;
long long a[],f[][],mmax;
int main()
{
long long i,j,k;
scanf("%lld%lld",&n,&m);
memset(f,,sizeof(f));
for(i=; i<=n; i++)
{
scanf("%lld",&a[i]);
mmax=max(mmax,a[i]);
}
for(i=a[]; i<=mmax; i++)
{
int s=i-a[];
f[][i]=s*s;
}
for(i=; i<=n; i++)
{
int p[],head=,tail=,mmin=;
for(j=a[i-];j<a[i];j++)
{
if(f[i-][j]+abs(a[i]-j)*m<f[i-][mmin]+abs(a[i]-mmin)*m||mmin==)
mmin=j;
}
int ssss=max(a[i],a[i-]);
p[++tail]=ssss;
for(j=ssss+;j<=mmax;j++)
{
while(f[i-][j]+abs(j-a[i])*m<f[i-][p[tail]]+abs(p[tail]-a[i])*m&&head<=tail)tail--;
p[++tail]=j;
}
for(j=a[i];j<=mmax;j++)
{
f[i][j]=min(f[i][j],f[i-][mmin]+abs(j-mmin)*m+(j-a[i])*(j-a[i]));
f[i][j]=min(f[i][j],f[i-][p[head]]+abs(j-p[head])*m+(j-a[i])*(j-a[i]));
if(f[i-][mmin]-abs(j-mmin)*m>f[i-][j])mmin=j;
if(p[head]==j)head++;
}
}
long long ans=1e18;
for(i=a[n]; i<=mmax; i++)
ans=min(ans,f[n][i]);
cout<<ans;
return ;
}