首页 > 代码库 > bzoj1564 二叉查找树

bzoj1564 二叉查找树

Description

技术分享

Input

技术分享

Output

只有一个数字,即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。

Sample Input

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

Sample Output

29

HINT

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

Source

http://www.lydsy.com/JudgeOnline/problem.php?id=1564

    这一道题我在听jiry上课时听过,但是却没有一遍过。

    事实上,我交了6遍RE才变成WA,然后又交了4遍WA才A了。。。。。。。

    不是我水平不行(其实是的),NOI的题太难了。

 

    我们切入正题,二叉查找树有两种方法可以解决,一种是数据结构,然而对于我们这种弱菜。。。。。

    另一种叫树形DP,勉强可以接受了。

    第一步:将权值按从小到大排序后用其在数组中编号来表示其权值

    第二步:

    既然是动态规划,方程是要列的

    

      首先我们对所有点的权值进行离散化,先前已经做过了,这样每个点的权值必然在区间[1,n中,用f[i][j][w来表示前序遍历中,区间[i,j对应的点作为一个子树,并且子树中所有权值都大于等于,这个子树访问代价与修改代价之和的最小值。

显然我们要枚举这个子树的根节点,那么有两种情况:1、点本来的权值是小于的,那么要符合小根堆的特性,点权值要修改为。2、点本来的权值就是大于等于的,那么可以选择不修改点的权值,也可以选择修改点的权值。

      然后得到方程

f[i][j][w]=min ik{f[i][k?1][w]+f[k+1][j][w]+K+∑ t=frequenc},weigh<
f[i][j][w]=min ik{f[i][k?1][weigh]+f[k+1][j][weigh]+∑ t=frequenc

     

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <string.h>
 5 #include <algorithm>
 6 
 7 #define MAXN 80
 8 
 9 using namespace std;
10 
11 struct Node
12 {
13     int val; //键值
14     int weight; //权值
15     int frequence; //频率
16 }node[MAXN];
17 
18 int n,K;
19 
20 bool cmp(Node a,Node b)
21 {
22     return a.val<b.val;
23 }
24 
25 int f[MAXN][MAXN][MAXN],stack[MAXN],top=0; //边界:f[i][i-1][w]=0,表示点i为根结点,下面无左儿子(i-1为根节点,下面无右儿子),显然f值为0
26 int sum[MAXN]; //频率的前缀和
27 
28 int main()
29 {
30     scanf("%d%d",&n,&K);
31     for(int i=1;i<=n;i++)
32         scanf("%d",&node[i].val);
33     for(int i=1;i<=n;i++)
34         scanf("%d",&node[i].weight),stack[++top]=node[i].weight;
35     for(int i=1;i<=n;i++)
36         scanf("%d",&node[i].frequence);
37     sort(stack+1,stack+top+1);
38     for(int i=1;i<=n;i++)
39         node[i].weight=lower_bound(stack+1,stack+top+1,node[i].weight)-stack;
40     sort(node+1,node+n+1,cmp);
41     for(int i=1;i<=n;i++)
42         sum[i]=sum[i-1]+node[i].frequence;
43     memset(f,0x3f,sizeof(f));
44     for(int i=1;i<=n+1;i++)
45         for(int w=0;w<=n;w++)
46             f[i][i-1][w]=0;
47     for(int w=n;w>=1;w--)
48         for(int i=n;i>=1;i--)
49             for(int j=i;j<=n;j++)
50                 for(int k=i;k<=j;k++) //枚举[i,j]这段区间的点对应的子树,该子树以点k作为根节点
51                 {
52                     f[i][j][w]=min(f[i][j][w],f[i][k-1][w]+f[k+1][j][w]+K+sum[j]-sum[i-1]); //k本来权值小于K,将其权值变为k
53                     if(node[k].weight>=w) f[i][j][w]=min(f[i][j][w],f[i][k-1][node[k].weight]+f[k+1][j][node[k].weight]+sum[j]-sum[i-1]); //k的权值本身就大于等于K,因此可以不变
54                 }
55     int ans=0x3f3f3f3f;
56     for(int w=0;w<=n;w++)
57         ans=min(ans,f[1][n][w]);
58     printf("%d\n",ans);
59     return 0;
60 }

PS:其实这个方程我也没列出来,最后看题解看了好久才看懂

bzoj1564 二叉查找树