bzoj1564

嗯，这是一道简单题

注意二叉搜索树的子树中序一定是连续的

又因为取值修改是任意的并且修改代价与权值无关

不难想到把权值离散化，然后按找数据值排序，然后dp

f[i][j][w]表示从i~j的节点构成一棵子树且所有节点权值都大于等于w的最小代价和

转移很明显，记忆化搜索即可

 const inf=;

 var f:array[..,..,..] of longint;

     s,a,b,c,d,p:array[..] of longint;

     i,n,m,k:longint;

 procedure min(var a:longint; b:longint);

   begin

     if a>b then a:=b;

   end;

 procedure swap(var a,b:longint);

   var c:longint;

   begin

     c:=a;

     a:=b;

     b:=c;

   end;

 procedure sort1(l,r:longint);

   var i,j,x:longint;

   begin

     i:=l;

     j:=r;

     x:=b[(l+r) shr ];

     repeat

       while b[i]<x do inc(i);

       while x<b[j] do dec(j);

       if not(i>j) then

       begin

         swap(b[i],b[j]);

         swap(d[i],d[j]);

         inc(i);

         dec(j);

       end;

     until i>j;

     if l<j then sort1(l,j);

     if i<r then sort1(i,r);

   end;

 procedure sort2(l,r:longint);

   var i,j,x:longint;

   begin

     i:=l;

     j:=r;

     x:=a[(l+r) shr ];

     repeat

       while a[i]<x do inc(i);

       while x<a[j] do dec(j);

       if not(i>j) then

       begin

         swap(a[i],a[j]);

         swap(c[i],c[j]);

         swap(p[i],p[j]);

         inc(i);

         dec(j);

       end;

     until i>j;

     if l<j then sort2(l,j);

     if i<r then sort2(i,r);

   end;

 function dp(l,r,m:longint):longint;

   var i:longint;

   begin

     if l>r then exit();

     if f[l,r,m]<>- then exit(f[l,r,m]);

     f[l,r,m]:=inf;

     for i:=l to r do

     begin

       min(f[l,r,m],dp(l,i-,m)+dp(i+,r,m)+k);

       if p[i]>=m then

         min(f[l,r,m],dp(l,i-,p[i]+)+dp(i+,r,p[i]+));

     end;

     f[l,r,m]:=f[l,r,m]+s[r]-s[l-];

     exit(f[l,r,m]);

   end;

 begin

   readln(n,k);

   for i:= to n do

   begin

     read(a[i]);

     d[i]:=i;

   end;

   for i:= to n do

     read(b[i]);

   for i:= to n do

     read(c[i]);

   sort1(,n);

   m:=;

   p[d[]]:=;

   for i:= to n do

   begin

     if b[i]<>b[i-] then inc(m);

     p[d[i]]:=m;

   end;

   sort2(,n);

   for i:= to n do

     s[i]:=s[i-]+c[i];

   fillchar(f,sizeof(f),);

   writeln(dp(,n,));

 end.