首页 > 代码库 > BZOJ 1564 二叉查找树

BZOJ 1564 二叉查找树

2024-07-08 23:51:19   220人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1564

题意：给出一棵treap，即每个点的数据 值、权值。根的数据值大于左孩子小于右孩子，根的权值比左右孩子都小。另外定义每个节点的访问次数，每个节点的代价为访问次数乘以深度（根深度为1）。整 棵树的代价为每个节点的代价和。现在可以修改节点的权值，每修改一个代价为K。要求最后整棵树的代价与修改代价最小。

思路：首先将权值离散化，将节点按照数据值排序。f[L][R][m]表示将区间[L,R]建立成满足题意的树，根节点的权值>=m的最小代价。那么对于每个区间，枚举每个点作为根节点，那么被枚举到的节点的权值要么修改，要么不修改。

 

i64 f[N][N][N];struct node{    int data,weight,freq;        int operator<(const node &a) const    {        return data<a.data;    }};node a[N];int n,K;int search(vector<int> V,int n,int x){    int low=0,high=n-1,mid;    while(low<=high)    {        mid=(low+high)>>1;        if(V[mid]==x) return mid;        if(V[mid]>x) high=mid-1;        else low=mid+1;    }}void up(i64 &x,i64 y){    if(y<x) x=y;}i64 DFS(int L,int R,int m){    if(L>R) return 0;    if(f[L][R][m]!=-1) return f[L][R][m];    i64 ans=inf;    int i;    for(i=L;i<=R;i++)    {        up(ans,DFS(L,i-1,m)+DFS(i+1,R,m)+K);        if(a[i].weight>=m)        {            up(ans,DFS(L,i-1,a[i].weight+1)+DFS(i+1,R,a[i].weight+1));        }    }    ans+=a[R].freq-a[L-1].freq;    return f[L][R][m]=ans;}int main(){    RD(n,K);    int i;    FOR1(i,n) RD(a[i].data);    FOR1(i,n) RD(a[i].weight);    FOR1(i,n) RD(a[i].freq);    sort(a+1,a+n+1);    vector<int> V;    FOR1(i,n) V.pb(a[i].weight);    sort(V.begin(),V.end());    FOR1(i,n) a[i].weight=1+search(V,n,a[i].weight);    FOR1(i,n) a[i].freq+=a[i-1].freq;    clr(f,-1);    PR(DFS(1,n,1));}

 

 

 


联系
我们