BZOJ 1564 二叉查找树

题目链接：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));
}