[bzoj1564]二叉查找树

题目描述

已知一棵特殊的二叉查找树。根据定义，该二叉查找树中每个结点的数据值都比它左儿子结点的数据值大，而比它右儿子结点的数据值小。

另一方面，这棵查找树中每个结点都有一个权值，每个结点的权值都比它的儿子结点的权值要小。

已知树中所有结点的数据值各不相同；所有结点的权值也各不相同。这时可得出这样一个有趣的结论：如果能够确定树中每个结点的数据值和权值，那么树的形态便可以唯一确定。因为这样的一棵树可以看成是按照权值从小到大顺序插入结点所得到的、按照数据值排序的二叉查找树。

一个结点在树中的深度定义为它到树根的距离加1。因此树的根结点的深度为1。

每个结点除了数据值和权值以外，还有一个访问频度。我们定义一个结点在树中的访问代价为它的访问频度乘以它在树中的深度。整棵树的访问代价定义为所有结点在树中的访问代价之和。

现在给定每个结点的数据值、权值和访问频度，你可以根据需要修改某些结点的权值，但每次修改你会付出K的额外修改代价。你可以把结点的权值改为任何实数，但是修改后所有结点的权值必须仍保持互不相同。现在你要解决的问题是，整棵树的访问代价与额外修改代价的和最小是多少？

输入输出格式

输入格式：

 

输入文件中的第一行为两个正整数N，K。其中：N表示结点的个数，K表示每次修改所需的额外修改代价。

接下来的一行为N个非负整数，表示每个结点的数据值。

再接下来的一行为N个非负整数，表示每个结点的权值。

再接下来的一行为N个非负整数，表示每个结点的访问频度。

其中：所有的数据值、权值、访问频度均不超过400000。每两个数之间都有一个空格分隔，且行尾没有空格。

 

输出格式：

 

输出文件中仅一行为一个数，即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。

 

输入输出样例

输入样例#1：

4 10
1 2 3 4
1 2 3 4
1 2 3 4

输出样例#1：

29

说明

【样例说明】

输入的原图是左图，它的访问代价是：1×1+2×2+3×3+4×4=30。

最佳的修改方案是把输入中的第3个结点的权值改成0，得到右图，访问代价是：1×2+2×3+3×1+4×2=19，加上额外修改代价10，一共是29。

【数据规模和约定】

对于40%的数据，满足：N<=30；

对于70%的数据，满足：N<=50；

对于100%的数据，满足：N<=70，1<=K<=30000000。

昨天的考试题。。。昨天不会，写了个rand100000次的萎烂做法，竟然此题得到了零分的好成绩！！！然后今天看了一遍题解。。。
和加分二叉树有点像。。。一个区间DP，因为树的中序遍历一定确定，所以只需在一个区间里枚举根，然后统计答案。。。状态就设f[i][j][e]为i~j的子树而且子树中所有权值都大于e的最小代价(所以需要离散化)。。。每个f需要加上这里面的访问频度，然后就可以一层一层加上去了。。。。。。
正确性的证明：不会

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
 
typedef long long ll;
il int gi(){
    rg int x=0;rg char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
struct node{ll d,w,n;}a[72];
il bool cmp(node kk,node kkk){return kk.w<kkk.w;}
il bool cmp2(node kk,node kkk){return kk.d<kkk.d;}
ll f[77][77][77];
ll num[77];
int main(){
    rg int n=gi();rg ll K=gi();
    rep(i,1,n)a[i].d=gi();
    rep(i,1,n)a[i].w=gi(),num[i]=a[i].w;
    rep(i,1,n)a[i].n=gi();
    sort(a+1,a+1+n,cmp2);
    rep(i,1,n)a[i].n+=a[i-1].n;
    sort(num+1,num+1+n);
    int mn=unique(num+1,num+1+n)-num-1;
    rep(i,1,n)a[i].w=lower_bound(num+1,num+1+mn,a[i].w)-num;
    rep(siz,0,n-1)rep(i,1,n-siz)rep(e,1,mn){
    ll&now=f[i][i+siz][e];now=2333333333333333333ll;
    rg int l=i,r=i+siz;
    rep(k,l,r){
            if(a[k].w>=e)now=min(now,f[l][k-1][a[k].w]+f[k+1][r][a[k].w]+a[r].n-a[l-1].n);
        now=min(now,K+f[l][k-1][e]+f[k+1][r][e]+a[r].n-a[l-1].n);
    }
    }
    ll ans=f[1][n][1];
    rep(i,2,mn)ans=min(ans,f[1][n][i]);
    printf("%lld\n",ans);
    return 0;
}