1845 二叉查找树

2009年NOI全国竞赛

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

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

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

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

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

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

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

输入描述 Input Description

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

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

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

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

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

输出描述 Output Description

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

样例输入 Sample Input

4 10

1 2 3 4

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【样例说明】

输入的原图是左图，它的访问代价是：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。

分类标签 Tags 点此展开

没看见图，理解的似懂非懂

思路：

先把权值离散化

按数据值排序

sum[i]为前i个节点频度和

dp[i][j][w]表示把节点[i,j]合并成一颗根节点权值不小于w的子树所需的访问代价与修改代价的最小和

dp[i][j][w]=min(dp[i][k-1][w]+dp[k+1][j][w]+sum[j]-sum[i-1]+K,dp[i][k-1][a[k].weight]+dp[k+1][j][a[k].weight]+sum[j]-sum[i-1](a[k].weight>=w))

(i<=k<=j)

ans=dp[1][n][1];

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 80
#define INF 0x3f3f3f3f
int n,m;
struct node{
    int key,weight,frequence;
}a[N];
int sum[N];
int dp[N][N][N];
bool cmp1(const node &A,const node &B){
    return A.weight<B.weight;
}
bool cmp2(const node &A,const node &B){
    return A.key<B.key;
}
int main()
{
    scanf("%d%d",&n,&m);
    int i,j,k,w,t;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i].key);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i].weight);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i].frequence);
    sort(a+1,a+n+1,cmp1);
    for(i=1;i<=n;i++)
        a[i].weight=i;
    sort(a+1,a+n+1,cmp2);
    sum[0]=0;
    for(i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i].frequence;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            if(a[i].weight>=j)
                dp[i][i][j]=a[i].frequence;
            else
                dp[i][i][j]=a[i].frequence+m;
        }
    for(w=n;w>=1;w--){
        for(t=1;t<n;t++){
            for(i=1;i+t<=n;i++){
                j=i+t;
                int s=INF;
                for(k=i;k<=j;k++){
                    s=min(s,dp[i][k-1][w]+dp[k+1][j][w]+sum[j]-sum[i-1]+m);
                    if(a[k].weight>=w)
                        s=min(s,dp[i][k-1][a[k].weight]+dp[k+1][j][a[k].weight]+sum[j]-sum[i-1]);
                }
                dp[i][j][w]=s;
            }
        }
    } 
    printf("%d
",dp[1][n][1]);
    return 0;
}