学步园

【题意】

有一列树，总共有n(n<=100000)棵，给定树的高度，要在相邻树和树之间架设电线，代价为c*（两树的高度差的绝对值），

但可以增高树的高度，需要代价为<增高高度的平方>

求最小代价

【输入】

多组数据

第一行为n、c

接下来一行为n个数，表示高度（高度小于等于100）

【输出】

对于每组数据输出一个数表示最小代价

dp

用f[i][j]表示第i棵树高度为j的时候的最小代价

很容易想到枚举相邻两棵树高度

这样复杂度是O(n*h*h)

会超时

从左往右扫描树的时候，首先做一个预处理，处理出来最小值，然后再用o（1）复杂度求解

答案或者中间值可能会溢出，所以需要用int64

program poj3612;
const
  thu:int64=1000;
var
  n,c,i,j,k,o,s,e:longint;
  ans:int64;
  h:array [0..100001] of longint;
  f:array [0..1,0..101] of int64;
  low,high:array [0..101] of int64;

function min (a,b:int64):int64;
begin
  if a<b then exit(a)
         else exit(b);
end;

function max (a,b:int64):int64;
begin
  if a>b then exit(a)
         else exit(b);
end;

begin
  while not seekeof do
    begin
      read(n,c);
      for i:=1 to n do
        read(h[i]);
      if n<=1 then
        begin
          writeln(0);
          continue;
        end;
      o:=1;
      for i:=0 to 101 do
        if i<h[1] then f[o,i]:=maxlongint*thu
                  else f[o,i]:=(h[1]-i)*(h[1]-i);
      ans:=maxlongint;
      for i:=2 to n do
        begin
          o:=1-o;
          fillchar(f[o],sizeof(f[o]),63);
          fillchar(low,sizeof(low),63);
          fillchar(high,sizeof(high),63);
          for j:=h[i-1] to 100 do
            low[j]:=min(low[j-1],f[1-o,j]-j*c);
          for j:=100 downto h[i] do
            high[j]:=min(high[j+1],f[1-o,j]+j*c);
          ans:=f[o,0];
          for j:=h[i] to 100 do
            begin
              f[o,j]:=min(low[j]+j*c,high[j]-j*c)+(j-h[i])*(j-h[i]);
              if i=n then ans:=min(ans,f[o,j]);
            end;
        end;
      writeln(ans);
    end;
end.