架设电话线
最近，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计算一下，如果合理地进行这两种工作，他最少要在这个电话线改造工程上花多少钱。
程序名: telewire
输入格式:
* 第1行: 2个用空格隔开的整数：N和C
* 第2..N+1行: 第i+1行仅有一个整数：height_i
输入样例 (telewire.in):
5 2
2
3
5
1
4
输入说明:
一共有5根电话线杆，在杆间拉电话线的费用是每米高度差$2。在改造之前，电话线杆的高度依次为2，3，5，1，4米。
输出样例:
* 第1行: 输出Farmer John完成电话线改造工程所需要的最小花费
输出样例 (telewire.out):
15
输出说明:
{zh0}的改造方法是：Farmer John把{dy}根电话线杆加高1米，把第四根加高2米，使得它们的高度依次为3，3，5，3，4米。这样花在加高电线杆上的钱是$5。此时，拉电话线的费用为$2*(0+2+2+1) = $10，总花费为$15。
一个易得的方程是f[i,j]表示第i个电线杆长度为j时的最小费用
f[i,j]:=min(f[i-1,k]+sqr(a[i]-j)+abs(j-k)*c);
观察方程可以转化为等价方程组
if j<=k 那么 f[i,j]:=min(f[i-1,k]+k*c)+sqr(a[i]-j)-j*c
if j>k 那么 f[i,j]:=min(f[i-1,k]-k*c)+sqr(a[i]-j)+j*c
而min(f[i-1,k]+k*c)与min(f[i-1,k]-k*c)是可以用滚动数组来搞定的
我的弱程序：（{zd0}居然0.59s TOT.........太弱了）
program telewire;
const
maxn=100001;
maxint=99999999;
var
f:array[-1..maxn,-1..101] of longint;
high,low:array[-1..100] of longint;
a:array[-1..maxn] of longint;
n,c,up,down:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure datain;
var
i,j:longint;
begin
assign(input,'telewire.in');reset(input);
assign(output,'telewire.out');rewrite(output);
readln(n,c);
up:=0;
down:=101;
for i:=1 to n do
begin
readln(a[i]);
if a[i]>up then up:=a[i];
if a[i]<down then down:=a[i];
end;
end;
procedure main;
var
i,j,k,ans:longint;
begin
for i:=-1 to maxn do
for j:=-1 to 101 do
f[i,j]:=maxint;
for i:=a[1] to 100 do
f[1,i]:=(a[1]-i)*(a[1]-i);
for k:=down to up do
low[k]:=maxint;
low[up]:=f[1,up]+up*c;
for k:=up-1 downto down do
low[k]:=min(low[k+1],f[1,k]+k*c);
for k:=down to up do
high[k]:=maxint;
high[down]:=f[i,down]-down*c;
for k:=down+1 to up do
high[k]:=min(high[k-1],f[1,k]-k*c);
for i:=2 to n do
begin
for j:=a[i] to up do
begin
f[i,j]:=low[j]+(a[i]-j)*(a[i]-j)-j*c;
f[i,j]:=min(f[i,j],high[j]+(a[i]-j)*(a[i]-j)+j*c);
end;
for k:=down to up do
low[k]:=maxint;
low[up]:=f[i,up]+up*c;
for k:=up-1 downto down do
low[k]:=min(low[k+1],f[i,k]+k*c);
for k:=down to up do
high[k]:=maxint;
high[down]:=f[i,down]-down*c;
for k:=down+1 to up do
high[k]:=min(high[k-1],f[i,k]-k*c);
end;
ans:=maxint;
for i:=down to up do
if ans>f[n,i] then ans:=f[n,i];
writeln(ans);
end;
begin
datain;
main;
close(input);
close(output);
end.
- <problem title="telewire" filename="telewire.pas" status="1" hash="1230896635" detail="">
<testcase status="7" exitcode="0" detail="" time="0.06" memory="41280" score="10" />
<testcase status="7" exitcode="0" detail="" time="0.06" memory="41280" score="10" />
<testcase status="7" exitcode="0" detail="" time="0.06" memory="41280" score="10" />
<testcase status="7" exitcode="0" detail="" time="0.04" memory="41280" score="10" />
<testcase status="7" exitcode="0" detail="" time="0.09" memory="41280" score="10" />
<testcase status="7" exitcode="0" detail="" time="0.09" memory="41280" score="10" />
<testcase status="7" exitcode="0" detail="" time="0.1" memory="41280" score="10" />
<testcase status="7" exitcode="0" detail="" time="0.18" memory="41280" score="10" />
<testcase status="7" exitcode="0" detail="" time="0.34" memory="41280" score="10" />
<testcase status="7" exitcode="0" detail="" time="0.57" memory="41280" score="10" />
