【NOI2009】二叉查找树

【问题描述】

　　已知一棵特殊的二叉查找树。根据定义，该二叉查找树中每个结点的数据值
都比它左子树结点的数据值大，而比它右子树结点的数据值小。
另一方面，这棵查找树中每个结点都有一个权值，每个结点的权值都比它的
儿子结点的权值要小。
已知树中所有结点的数据值各不相同；所有结点的权值也各不相同。这时可
得出这样一个有趣的结论：如果能够确定树中每个结点的数据值和权值，那么树
的形态便可以唯一确定。因为这样的一棵树可以看成是按照权值从小到大顺序插
入结点所得到的、按照数据值排序的二叉查找树。
一个结点在树中的深度定义为它到树根的距离加 1。因此树的根结点的深度
为 1。
　　每个结点除了数据值和权值以外，还有一个访问频度。我们定义一个结点在
树中的访问代价为它的访问频度乘以它在树中的深度。整棵树的访问代价定义为
所有结点在树中的访问代价之和。
　　现在给定每个结点的数据值、权值和访问频度，你可以根据需要修改某些
结点的权值，但每次修改你会付出 K 的额外修改代价。你可以把结点的权值改
为任何实数，但是修改后所有结点的权值必须仍保持互不相同。现在你要解决的
问题是，整棵树的访问代价与额外修改代价的和最小是多少？
【输入格式】
输入文件为 treapmod.in。
输入文件第一行包含两个正整数 N 和 K。 N 为结点的个数， K 为每次
修改所需的额外修改代价。
接下来一行包含 N 个非负整数，是每个结点的数据值。
再接下来一行包含 N 个非负整数，是每个结点的权值。
再接下来一行包含 N 个非负整数，是每个结点的访问频度。
所有的数据值、权值、访问频度均不超过 400000。每两个数之间都有一个
空格分隔，且行尾没有空格。
【输出格式】
输出文件为 treapmod.out。
输出文件只有一个数字，即你所能得到的整棵树的访问代价与额外修改代价
之和的最小值。
【样例 1 输入】
4 10
1 2 3 4
1 2 3 4
1 2 3 4
【样例 1 输出】
29
第 6 页共 8 页
【样例 1 说明】
输入的原图是左图，它的访问代价是 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。

【题解】

　　数据值已经确定了，那么这棵树的中序遍历就已经确定了，我们相当于改变权值来改变深度。

　　而权值可以是任意实数，但是却和答案无关，我们完全可以离散化一下。

　　那么我们设dp[i][j][w]表示以区间[i,j]内的节点为树，根节点都>=w的方案总数。

　　我们通过枚举区间内的根k，可以写出转移方程（sum(i,j)表示[i，j]的访问频率和）。

　　当k>=w时，我们就可以把k之间弄成根，dp[i][j][w]=min(dp[i][k-1][w_k]+dp[k+1][j][w_k]+sum(i,j));

　　也可以把k的权值修改成w,dp[i][j][w]=min(dp[i][k-1][w]+dp[k+1][w]+K+sum(i,j));

　　因为如果直接dp偏序关系不太明确，在实现时可以使用记忆化搜索。（表示一开始直接dp调了一个上午没调出来）

【Code】

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

#define ll long long

#define REP(i,a,b) for(register int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(register int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,a) for(register int i=start[(a)];i;i=e[i].next)

inline int read()

{

    int sum=,p=;char ch=getchar();

    while(!((''<=ch && ch<='') || ch=='-'))ch=getchar();

    if(ch=='-')p=-,ch=getchar();

    while(''<=ch && ch<='')sum=sum*+ch-,ch=getchar();

    return sum*p;

}

const int maxn=;

int n,K;

struct node {

    int a,b,c;

};

node g[maxn];

bool cmp (const node x,const node y)

{

    return x.a<y.a;

}

int Sum(int x,int y)

{

    return g[y].c-g[x-].c;

}

void init()

{

    int s[maxn];

    n=read();K=read();

    REP(i,,n)g[i].a=read();

    REP(i,,n)g[i].b=read(),s[i]=g[i].b;

    REP(i,,n)g[i].c=read();

    sort(g+,g+n+,cmp);

    sort(s+,s+n+);

    int cnt=unique(s+,s+n+)-(s+);

    REP(i,,n)

    {

        REP(j,,cnt)

        {

            if(g[i].b==s[j]){g[i].b=j;break;}

        }

    }

    REP(i,,n)g[i].c+=g[i-].c;

}

ll dp[maxn][maxn][maxn];

void chkmin(ll &a,ll b)

{

    if(a>b)a=b;

}

#define inf 0x7ffffffffff

ll dfs(int l,int r,int k)

{

    if(l>r)return ;

    if(~dp[l][r][k])return dp[l][r][k];

    ll ans=inf;

    REP(i,l,r)

    {

        chkmin(ans,dfs(l,i-,k)+dfs(i+,r,k)+K);

        if(g[i].b>=k)chkmin(ans,dfs(l,i-,g[i].b)+dfs(i+,r,g[i].b));

    }

    return dp[l][r][k]=ans+Sum(l,r);

}

void doing()

{

    memset(dp,-,sizeof(dp));

    //REP(i,1,n)dp[i][i][g[i].b]=Sum(i,i);

    /*REP(len,1,n-1)

    {

        REP(i,1,n-len)

        {

            int j=i+len;

            REP(k,1,Min(i,j))

            {

                REP(l,i,j)

                {

                    int Mn=Min(i,j),z=0;

                    if(Mn==g[l].b)z=0;else z=K;

                    chkmin(dp[i][j][k],dp[i][l-1][Mn]+dp[l+1][j][Mn]+z+Sum(i,j));

                }

            }

        }

        }*/

    cout<<dfs(,n,)<<endl;

}

int main()

{

    init();

    doing();

    return ;

}

巴特西

NOI2009 二叉查找树【区间dp】

【NOI2009】二叉查找树

【问题描述】

【题解】

【Code】

最新文章

热门文章

巴特西

NOI2009 二叉查找树 【区间dp】

【NOI2009】二叉查找树

【问题描述】

【题解】

【Code】

最新文章

热门文章

NOI2009 二叉查找树【区间dp】