dp。
首先这棵树是一个treap。
权值我们可以改成任意实数，所以权值只表示相互之间的大小关系，可以离散化。
树的中序遍历是肯定确定的。
用f[l][r][w]表示中序遍历为l到r，根的权值必须大于w的最小代价。
当a[x].w<=w时有f[l][r][w]=min(f[l][x-1][w]+f[x+1][r][w]+s[l][r]+k).s[i][j]表示从l到r访问次数的和。
当a[x].w>w时，还有f[l][r][w]=min(f[l][x-1][w]+f[x+1][r][w]+s[l][r]).不用修改了。
对于[1,n]来说，根的权值只存在改和不改俩种状态。所以res=min(f[1][n][0],f[1][n][1])。
必须是这俩个取min，如果只取0的话，就会忽略根为原树的根的答案。
否则就会忽略根不为原树的答案（这不是废话么。。其实因为新根能改为小于1，如果只能改为1的话，原根的权值还要变大）。
用一个res作为引用可以不用打那么一长串（膜lrj巨神）
#include<cstdio> #include<algorithm> #include<cstring> #define LL long long using namespace std; const int maxn = 70 + 10; const LL inf = 0x3f3f3f3f3f3f3f3fll; struct Point { int v,w,d; }a[maxn]; int n,k; LL f[maxn][maxn][maxn],s[maxn],res; bool cmp1(Point p1,Point p2) { return p1.w<p2.w; } bool cmp2(Point p1,Point p2) { return p1.v<p2.v; } LL DP(int l,int r,int w) { if(l>r) return 0; if(f[l][r][w]!=inf) return f[l][r][w]; for(int x=l;x<=r;x++) { LL& res=f[l][r][w]; res=min(res,DP(l,x-1,w)+DP(x+1,r,w)+s[r]-s[l-1]+k); if(a[x].w>w) res=min(res,DP(l,x-1,a[x].w)+DP(x+1,r,a[x].w)+s[r]-s[l-1]); } return f[l][r][w]; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i].v); for(int i=1;i<=n;i++) scanf("%d",&a[i].w); for(int i=1;i<=n;i++) scanf("%d",&a[i].d); sort(a+1,a+n+1,cmp1); for(int i=1;i<=n;i++) a[i].w=i; sort(a+1,a+n+1,cmp2); for(int i=1;i<=n;i++) { a[i].v=i; s[i]=s[i-1]+a[i].d; } memset(f,0x3f,sizeof(f)); printf("%lld\n",min(DP(1,n,0),DP(1,n,1))); return 0; }
原文：http://www.cnblogs.com/invoid/p/5658724.html