C3-Zexal的OBST

题目描述

假设给定一个n个不同关键字的严格升序序列K=<k[1], k[2], …, k[n]>，用这些关键字构造二叉搜索树。对关键字k[i]，有p[i]次被检索到。有些搜索的值可能不在K中，假设n+1个伪关键字D=<d[0], d[1], …, d[n]>，对i=1, 2, ..., n-1，d[i]表示在k[i]和k[i+1]之间的值，d[0]表示小于k[1]的值，d[n]表示大于k[n]的值。对每个伪关键字d[i]，有q[i]次被检索到。请注意这里规定了每个关键字和伪关键字的检索次数。

用上述D序列作叶节点，K序列做内部节点，（可以参考算法导论第三版中文版226-230页，但注意题目定义的不同之处）构造一棵最优二叉搜索树。假设根节点深度为1，给定p, q，求出这二叉搜索棵树的最小总代价。

总代价定义为下面两式之和：

输入

第一行两个整数n。 $1 \leq n \leq 500$

第二行n个整数 $p [i]$

第三行n+1个整数 $q [i]$

输出

一个整数，表示最小总代价。

输入样例

5
15 10 5 10 20
5 10 5 5 5 10

输出样例

代码

 1 #include <iostream>
 2 #include <iomanip>
 3 #include <cstring>
 4 #include<cstdio>
 5 #define N 505
 6 using namespace std;
 7 typedef int T;
 8 int a[N],b[N];
 9 T w[N][N],q[N],p[N],e[N][N];
10 int r[N][N];
11 int n;
12 T dep;
13 void PRINT_OPTIMAL_BST(int i,int j,T depth)
14 {
15     if(i == 1 && j == n)
16         {
17            // cout <<"k"<<r[i][j]<<" is the root"<<endl;
18             dep += p[r[i][j]];
19         }
20     if(i == j )
21     {
22         //cout<<"d"<<i-1<<" is the left child of k"<<i<<endl;
23         dep += depth*q[i-1];
24         //cout<<"d"<<i<<" is the right child of k"<<i<<endl;
25         dep += depth*q[i];
26     }
27     else if(r[i][j] == i)
28     {
29         //cout<<"d"<<i-1<<" is the left child of k"<<i<<endl;
30         dep += depth*q[i-1];
31         //cout<<"k"<<r[i+1][j]<<" is the right child of k"<<r[i][j]<<endl;
32         dep += depth*p[r[i+1][j]];
33         PRINT_OPTIMAL_BST(i+1,j,depth+1);
34     }
35     else if(r[i][j] == j)
36     {
37         //cout<<"k"<<r[i][j-1]<<" is the left child of k"<<r[i][j]<<endl;
38         dep += depth*p[r[i][j-1]];
39         PRINT_OPTIMAL_BST(i,j-1,depth+1);
40         //cout<<"d"<<j<<" is the right child of k"<<j<<endl;
41         dep += depth*q[j];
42     }
43     else
44     {
45         //cout<<"k"<<r[i][r[i][j]-1]<<" is the left child of k"<<r[i][j]<<endl;
46         dep += depth*p[r[i][r[i][j]-1]];
47         PRINT_OPTIMAL_BST(i,r[i][j]-1,depth+1);
48         //cout<<"k"<<r[r[i][j]+1][j]<<" is the right child of k"<<r[i][j]<<endl;
49         dep += depth*p[r[r[i][j]+1][j]];
50         PRINT_OPTIMAL_BST(r[i][j]+1,j,depth+1);
51     }
52 }
53 void OPTIMAL_BST()
54 {
55     for(int i = 1; i <= n+1; i++)
56     {
57         e[i][i-1] = w[i][i-1] = q[i-1];
58     }
59     for(int l = 1; l <= n; l++)
60     {
61         for(int i = 1; i <= n-l+1; i++)
62         {
63             int j = i+l-1;
64             e[i][j] = 0x7ffffff;
65             w[i][j] = w[i][j-1] + p[j]+q[j];
66             for(int k = i ; k <= j ; k++)
67             {
68                 T t = e[i][k-1]+e[k+1][j]+w[i][j];
69                 if(t < e[i][j])
70                 {
71                     e[i][j] = t;
72                     r[i][j] = k;
73                 }
74             }
75         }
76     }
77     PRINT_OPTIMAL_BST(1,n,2);
78 }
79 
80 int main()
81 {
82     while(cin>>n)
83     {
84         memset(w,0,sizeof(w));
85         memset(e,0,sizeof(e));
86         memset(r,0,sizeof(r));
87         dep = 0;
88         int sum = 0;
89         for(int i = 1; i <= n; i++) cin>>p[i],sum+=p[i];
90         for(int i = 0; i <= n; i++) cin >>q[i],sum+=q[i];
91         //for(int i = 1; i <= n; i++) p[i]=(float)a[i]/(float)sum;
92         //for(int i = 0; i <= n; i++) q[i]=(float)b[i]/(float)sum;
93         OPTIMAL_BST();
94         printf("%d
",(int)(dep));
95     }
96 
97     return 0;
98 }