题解 P2545 【[AHOI2004]实验基地】

· · 题解

//个人觉得这道题的重点就在求第一层每个区间的最小值、

//可以用DP来求解、
//F[I,J]=MIN(F[I,J-1],F[I+1,J])
//剩下的很简单了、
const maxn=2001;
var  n,i,j,ans,z,k:longint;
     s,b:array[0..maxn] of longint;
     a:array[1..2,0..maxn] of longint;
     f:array[0..maxn,0..maxn] of longint;
function max(a,b:longint):longint;
begin
        if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
        if a<b then exit(a) else exit(b);
end;
begin
        readln(n);
        for i:=1 to 2 do
                for j:=1 to n do
                read(a[i,j]);
        for i:=1 to n do
        begin
                s[i]:=s[i-1]+a[1,i]+a[2,i];
                b[i]:=b[i-1]+a[1,i];
        end;
        for k:=1 to n-2 do
        for i:=2 to n-k do
        begin
                j:=i+k-1;
                f[i,j]:=min(min(f[i,j-1],f[i+1,j]),b[j]-b[i-1]);
        end;
        for i:=1 to n-2 do
        for j:=i+2 to n do
                ans:=max(ans,s[j]-s[i-1]-f[i+1,j-1]);
        writeln(ans);
end.
type link=^node; 
     node=record 
      data,h:longint;{储存的值和高度} 
      l,r:link;{左右子树的地址} 
     end;{树的定义} 
var i,j,k,m,n,t,l,r:longint; 
    biao:array[1..maxint] of link;{左偏森林} 
    q,g,tree:link;{g是空指针q是用来操作的指针} 
procedure swap(var aa,bb:link);{交换指针} 
var cc:link; 
begin 
 cc:=aa; 
 aa:=bb; 
 bb:=cc; 
end; 
function min(aldi,bldi:longint):longint;{较小值} 
begin 
 if aldi>bldi then 
        exit(bldi) 
 else   exit(aldi); 
end; 
function union(x,y:link):link;{合并操作} 
begin 
 if x=g then exit(y); 
 if y=g then exit(x);{一者空则返回令一者} 
 if x^.data>y^.data then 
        swap(x,y);{使得x指向较小的根y指向较大的根} 
 x^.r:=union(x^.r,y);{合并x的左子树和y到x的左子树} 
 x^.h:=min(x^.l^.h,x^.r^.h)+1;{维护高度}{若是权重树则x^.h:=x^.l^.h+x^.r^.h+1} 
 if x^.l^.h<x^.r^.h then 
        swap(x^.l,x^.r);{维护左子树大于等于右子树的性质} 
 exit(x);{返回} 
end; 
procedure init;{输入} 
begin 
 readln(n); 
 new(g); 
 g^.l:=g; 
 g^.r:=g; 
 g^.data:=0; 
 g^.h:=0;{初始化空指针} 
 for i:=1 to n do 
  begin 
         read(t); 
         new(q); 
         q^.data:=t; 
         q^.l:=g; 
         q^.r:=g; 
         q^.h:=1; 
         biao[i]:=q; 
        end;{建立森林} 
 l:=1; 
 r:=n;{队列的首末指针} 
end; 
function chu(var head:link):longint;{删除并返回最小根} 
begin 
  chu:=head^.data; 
  dispose(head); 
  head:=union(head^.l,head^.r); 
end; 
procedure print(qq:link);{从小到大输出} 
begin 
  for i:=1 to n do 
        begin 
         t:=chu(qq); 
         write(t,' '); 
        end; 
  writeln; 
end; 
procedure suan; 
begin 
 while l<r-1 do{初始化} 
        begin 
         q:=union(biao[l mod maxint],biao[(l+1) mod maxint]); 
         inc(l,2); 
         inc(r); 
         biao[r]:=q; 
        end;{一次合并两个以获得更快的效率}{这里相当于队列} 
 if l=r-1 then 
        tree:=union(biao[l mod maxint],biao[(l+1) mod maxint]){剩两棵} 
 else   tree:=biao[l mod maxint];{只剩一棵} 
 print(tree);{打印} 
end; 
Begin 
 init; 
 suan;
end.