bzoj1835

最近状态太差，先补补结题报告吧
这是一道好题
设f[i,j]表示到第j个位置建了i个基站且第j个位置建了基站的最小花费
不难得到f[i,j]=min(f[i-1,k]+cost[k+1,j])+c[j];
首先为了方便计算假定在两端无穷远处还要建一个基站（方便统计）
i我们是可以滚动的不管他，问题就是如何解决cost
也就是两个基站间的村庄的补偿费
我们设每个村庄i向左最远能收到l[i]位置上基站的信号，向右最远r[i]
不难发现，随着j的递增，cost[k]是呈上升趋势的
也就是，对于当前j，那些r[p]<j的点p，向右是永远收不到信号了，
向左对于在位置k∈[0,l[p]-1]的基站，随着j增加以k,j为端点建基站对于p是永远要收补偿费的
于是我们令cost[k]表示（k建基站）到当前点之间村庄要收补偿费的和
对于当前点j，我们找出r[p]+1=j的点p，对于k∈[0,l[p]-1] cost[k]+w[p]
显然是区间查询，区间修改的问题，我们可以用线段树解决
复杂度O(knlogn)

 type node=record

        po,next:longint;

      end;

 var f,c,d,p,w,s,l:array[..] of longint;

     e:array[..] of node;

     tree,lazy:array[..*] of longint;

     ans,n,m,i,j,k,t,x:longint;

 function min(a,b:longint):longint;

   begin

     if a>b then exit(b) else exit(a);

   end;

 procedure update(i:longint);

   begin

     tree[i]:=min(tree[i*],tree[i*+]);

   end;

 procedure push(i:longint);

   begin

     inc(lazy[i*],lazy[i]);

     inc(lazy[i*+],lazy[i]);

     inc(tree[i*],lazy[i]);

     inc(tree[i*+],lazy[i]);

     lazy[i]:=;

   end;

 function fl(l,r,x:longint):longint;

   var m:longint;

   begin

     fl:=r;

     while l<=r do

     begin

       m:=(l+r) shr ;

       if d[m]>=x then

       begin

         fl:=m;

         r:=m-;

       end

       else l:=m+;

     end;

   end;

 function fr(l,r,x:longint):longint;

   var m:longint;

   begin

     fr:=l;

     while l<=r do

     begin

       m:=(l+r) shr ;

       if d[m]<=x then

       begin

         fr:=m;

         l:=m+;

       end

       else r:=m-;

     end;

   end;

 procedure build(i,l,r:longint);

   var m:longint;

   begin

     lazy[i]:=;

     if l=r then

     begin

       tree[i]:=f[l];

       lazy[i]:=;

     end

     else begin

       m:=(l+r) shr ;

       build(i*,l,m);

       build(i*+,m+,r);

       update(i);

     end;

   end;

 procedure work(i,l,r,x,y:longint);

   var m:longint;

   begin

     if r<=x then

     begin

       inc(lazy[i],y);

       inc(tree[i],y);

     end

     else begin

       if lazy[i]<> then push(i);

       m:=(l+r) shr ;

       work(i*,l,m,x,y);

       if x>m then work(i*+,m+,r,x,y);

       update(i);

     end;

   end;

 function ask(i,l,r,x:longint):longint;

   var m,s:longint;

   begin

     if r<=x then exit(tree[i])

     else begin

       if lazy[i]<> then push(i);

       m:=(l+r) shr ;

       s:=ask(i*,l,m,x);

       if x>m then s:=min(s,ask(i*+,m+,r,x));

       exit(s);

     end;

   end;

 begin

   readln(n,m);

   for i:= to n do

     read(d[i]);

   for i:= to n do

     read(c[i]);

   for i:= to n do

     read(s[i]);

   for i:= to n do

   begin

     read(w[i]);

     ans:=ans+w[i];

   end;

   for i:= to n do

   begin

     l[i]:=fl(,i,d[i]-s[i]);

     x:=fr(i,n,d[i]+s[i]);

     inc(t);

     e[t].po:=i;

     e[t].next:=p[x+];

     p[x+]:=t;

   end;

   for i:= to m do

   begin

     build(,,n);

     for j:= to n+ do

     begin

       k:=p[j];

       while k<> do

       begin

         work(,,n,l[e[k].po]-,w[e[k].po]);

         k:=e[k].next;

       end;

       if i= then x:= else x:=j-;

       f[j]:=ask(,,n,x)+c[j];

     end;

     ans:=min(ans,f[n+]);

   end;

   build(,,n);

   for j:= to n+ do

   begin

     k:=p[j];

     while k<> do

     begin

       work(,,n,l[e[k].po]-,w[e[k].po]);

       k:=e[k].next;

     end;

   end;

   ans:=min(ans,ask(,,n,n));

   writeln(ans);

 end.

巴特西

bzoj1835

最新文章

热门文章