C3-Zexal的OBST

题目描述

假设给定一个n个不同关键字的严格升序序列K=，用这些关键字构造二叉搜索树。对关键字k[i]，有p[i]次被检索到。有些搜索的值可能不在K中，假设n+1个伪关键字D=，对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≤n≤500">1≤n≤5001≤n≤500

第二行n个整数 p[i]">p[i]p[i]，表示关键字的出现次数。

第三行n+1个整数q[i]">q[i]q[i]，表示i-1关键字与i关键字之间的出现次数。0≤p[i],q[i]≤1000">0≤p[i],q[i]≤10000≤p[i],q[i]≤1000

输出

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

输入样例

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

输出样例

275

代码

 1 #include 
 2 #include 
 3 #include 
 4 #include
 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"<
18             dep += p[r[i][j]];
19         }
20     if(i == j )
21     {
22         //cout<<"d"<
23         dep += depth*q[i-1];
24         //cout<<"d"<
25         dep += depth*q[i];
26     }
27     else if(r[i][j] == i)
28     {
29         //cout<<"d"<
30         dep += depth*q[i-1];
31         //cout<<"k"<
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"<
38         dep += depth*p[r[i][j-1]];
39         PRINT_OPTIMAL_BST(i,j-1,depth+1);
40         //cout<<"d"<
41         dep += depth*q[j];
42     }
43     else
44     {
45         //cout<<"k"<
46         dep += depth*p[r[i][r[i][j]-1]];
47         PRINT_OPTIMAL_BST(i,r[i][j]-1,depth+1);
48         //cout<<"k"<
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\n",(int)(dep));
95     }
96 
97     return 0;
98 }