首先，将权值离散化，即将节点的权值按顺序依次设为1,2,3,4,5,6..........

将节点的数据值sort,定义状态f(i,j,k)为由第i个节点到第j个节点组成的treap,根节点的权值大于k

首先，假设由i到j的treap中根节点为o:

(1)若不改变t[o],则必须满足t[o]>=k.则t[L[o]]>=t[o]且t[R[o]]>=t[o],则这个treap的费用为f[i,o-1,t[o]]+f[o+1,j,t[o]]+sum(p[i..j]）

(2)若将t[o]变为k，又因为t[o]<>k，则t[o]=k+c(c为很小很小的常数），则可设t[L[o]]>=k+c,t[R[o]]>=k+c,且都不为整数（纠结！权值可以不是整数），可以看做都大于等于k，则费用为f[i,o-1,k]+f[o+1,j,k]+sum(p[i..j])+cost(cost为节点改权的费用）.

在这里c并不重要，所以可以忽略。

状态转移方程如下：

f[i,j,k]=min{f[i,o-1,k]+f[o+1,j,k]+sum(p[i..j])+cost,

                 f[i,o-1,t[o]+f[o+1,j,t[o]]+sum(p[i..j])}(i<=o<=j)

边界处理：f[i,i-1,k]=0,对于f[i,i,k]

若t[i]>=k则无改权的必要，可设f[i,i,k]=p[i]

若t[i]<k则必须改权，设f[i,i,k]=p[i]+cost

输出f[1,n,0]即可，时间复杂度为O(n^4)，空间复杂度为O(n^3)。

My code:

{$M 16777216}
program treapmod;
var i,j,k,l,m,n,cost:longint;
    limit:qword;
    a:array[0..80,0..80,0..80] of qword;
    t,b,w,p:array[0..80] of longint;
procedure init;
var i,j,k:longint;
begin
    assign(input,'treapmod.in');
    assign(output,'treapmod.out');
    reset(input);
    rewrite(output);
    readln(n,cost);
    for i:=1 to n do read(w[i]);readln;
    for i:=1 to n do read(t[i]);readln;
    for i:=1 to n do begin
      read(p[i]);
    end;readln;
    close(input);
    limit:=1<<62;
end;

procedure swap(var i,j:longint);
var k:longint;
begin
    k:=i;i:=j;j:=k;
end;

function sum(i,j:longint):longint;
begin exit(p[j]-p[i-1]);end;

function min(i,j:qword):qword;
begin if i<j then exit(i) else exit(j);end;

procedure doit;
var i,j,k,l:longint;
begin
    for i:=1 to n do
      for j:=i+1 to n do
        if w[i]>w[j] then begin
          swap(w[i],w[j]);
          swap(t[i],t[j]);
          swap(p[i],p[j]);
        end;
    for i:=1 to n do inc(p[i],p[i-1]);
    for i:=1 to n do b[i]:=i;
    for i:=1 to n do
      for j:=i+1 to n do if t[b[i]]>t[b[j]] then
        swap(b[i],b[j]);
    for i:=1 to n do t[b[i]]:=i;
    for i:=1 to n do
      for j:=i+1 to n do if w[b[i]]>w[b[j]] then
        swap(b[i],b[j]);
    for i:=1 to n do
      for j:=0 to n do
        if t[i]>=j then a[i,i,j]:=sum(i,i) else a[i,i,j]:=sum(i,i)+cost;
    for i:=1 to n-1 do
      for j:=1 to n-i do
        for k:=0 to n do begin
          a[j,j+i,k]:=limit;
          for l:=j to j+i do begin
            if t[l]>=k then a[j,j+i,k]:=min(a[j,j+i,k],a[j,l-1,t[l]]+a[l+1,j+i,t[l]]+sum(j,j+i));
            a[j,j+i,k]:=min(a[j,j+i,k],a[j,l-1,k]+a[l+1,j+i,k]+sum(j,j+i)+cost);
          end;
        end;
end;

procedure upit;
var i,j,k:longint;
begin
    writeln(a[1,n,0]);
    close(output);
end;
{------------------------------main------------------------------------}
begin
init;
doit;
upit;
end.

窘错误：

（1）我本能的吧sum写到init里了，结果sort后就傻了，我是个傻子

（2）我排完权值后忘排数据值了，结果又傻了。。

（3）原来权值可以不是整数。。。。。