最优二叉搜索树（Optimal BST）解题报告

这个问题要求我们构造一棵二叉搜索树（BST），使得给定查询概率下的期望比较次数最小。这是一个经典的动态规划问题，称为最优二叉搜索树（Optimal BST）问题。

问题分析

基本概念

• 二叉搜索树（BST）：每个节点的左子树中的所有节点标签都小于该节点，右子树中的所有节点标签都大于该节点。
• 中序遍历：BST的中序遍历会按字典序输出节点标签。
• 最优BST：给定查询概率，使得期望比较次数最小的BST。

关键定义

• 内部节点概率：p[i] 表示查询第 i 个关键字的概率。
• 外部节点概率：q[i] 表示查询落在第 i 个关键字和第 i+1 个关键字之间的概率。
• 成本函数：期望比较次数，由内部节点和外部节点的层级加权求和。

动态规划思路

我们需要找到一种BST结构，使得以下成本函数最小化：

cost = ∑(p[i] * (1 + 内部节点K[i]的层级)) + ∑(q[i] * (外部节点的层级))

解题思路

这个问题可以使用动态规划结合Knuth优化来解决。核心思路如下：

1. 状态定义：

   • f[i][j] 表示包含关键字 K[i..j] 的子树的最小成本。
   • s[i][j] 记录最优根节点，用于Knuth优化。

2. 状态转移：

   • 对于每个子树 [i..j]，尝试所有可能的根节点 k，计算以 k 为根的子树的成本，并取最小值。

3. Knuth优化：

   • 观察到最优根节点 s[i][j] 满足单调性：s[i][j-1] ≤ s[i][j] ≤ s[i+1][j]。
   • 利用这一性质，将枚举根节点的范围从 [i..j] 缩小到 [s[i][j-1]..s[i+1][j]]，时间复杂度从 O(n³) 降至 O(n²)。

代码分析

以下是完整的代码实现：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define RG register
using namespace std;
typedef long long ll;
const int N=405;
ll n,p[N],q[N],f[N][N],s[N][N];
int main()
{
    while(scanf("%lld",&n)==1){
        if(!n)break;
        // 输入并计算前缀和
        for(RG int i=1;i<=n;i++)scanf("%lld",&p[i]),p[i]+=p[i-1];
        for(RG int i=0;i<=n;i++)scanf("%lld",&q[i]),q[i]+=q[i-1];
        
        // 初始化动态规划数组
        memset(f,63,sizeof(f));
        for(RG int i=1;i<=n;i++){
            f[i][i]=q[i]+p[i]-p[i-1];
            s[i][i]=i;
            if(i>=2)f[i][i]-=q[i-2];
        }
        for(RG int i=1;i<=n+1;i++)f[i][i-1]=0;
        
        // 动态规划计算
        for(RG int l=2;l<=n;l++)
            for(RG int i=1;l+i-1<=n;i++)
                for(RG int k=s[i][i+l-2];k<=s[i+1][i+l-1];k++)
                    if(i>=2){
                        f[i][l+i-1]=min(f[i][l+i-1],f[i][k-1]+f[k+1][l+i-1]+p[l+i-1]-p[i-1]+q[l+i-1]-q[i-2]);
                        if(f[i][l+i-1]==f[i][k-1]+f[k+1][l+i-1]+p[l+i-1]-p[i-1]+q[l+i-1]-q[i-2])s[i][l+i-1]=k;
                    }
                    else {
                        f[i][l+i-1]=min(f[i][l+i-1],f[i][k-1]+f[k+1][l+i-1]+p[l+i-1]-p[i-1]+q[l+i-1]);
                        if(f[i][l+i-1]==f[i][k-1]+f[k+1][l+i-1]+p[l+i-1]-p[i-1]+q[l+i-1])s[i][l+i-1]=k;
                    }
        printf("%lld\n",f[1][n]);
    }
    return 0;
}

关键部分解析

1. 输入处理与前缀和：

   • 输入 p 和 q 数组，并直接计算前缀和，便于后续区间求和。

2. 初始化：

   • f[i][i] 表示只包含一个关键字的子树的成本。
   • f[i][i-1] = 0 处理空区间的情况。

3. 动态规划：

   • 外层循环 l 控制子树的长度。
   • 中层循环 i 控制子树的起始位置。
   • 内层循环 k 枚举可能的根节点，使用Knuth优化缩小枚举范围。

4. 成本计算：

   • 对于每个可能的根节点 k，计算其左右子树的成本，并加上当前子树的总概率。
   • 总概率通过前缀和快速计算，避免重复求和。

5. Knuth优化：

   • 使用 s[i][j] 记录最优根节点，将枚举范围从 [i..j] 优化到 [s[i][j-1]..s[i+1][j]]。

复杂度分析

• 时间复杂度：O(n²)，得益于Knuth优化，将原本的O(n³)时间复杂度降至O(n²)。
• 空间复杂度：O(n²)，主要用于存储动态规划数组和最优根节点数组。

这个算法高效地解决了最优二叉搜索树问题，确保在给定查询概率下的期望比较次数最小。

#include <iostream>
#include <iterator>
#include <sstream>
#include <fstream>
#include <istream>
#include <ostream>
#include <complex>
#include <cstring>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <new>
#include <set>
#include <map>
 
using namespace std;
 
 
const int maxn = 300;
const int INF = 0x3f3f3f3f;
 
int main()
{
 
    //freopen("1.txt", "r", stdin);
    int n, p[maxn], q[maxn], w[maxn][maxn], e[maxn][maxn];
    while (scanf("%d", &n), n)
    {
        for (int i=1; i<=n; i++)
            scanf("%d", &p[i]);
        for (int i=0; i<n+1; i++)
            scanf("%d", &q[i]);
        for (int i=1; i<=n+1; i++)
        {
            e[i][i - 1] = 0;
            w[i][i - 1] = q[i - 1];
        }
        for (int l=1; l<=n; l++)
            for (int i=1; i<=n-l+1; i++)
            {
                int j = i + l - 1;
                e[i][j] = INF;
                w[i][j] = w[i][j - 1] + p[j] + q[j];
                for (int r=i; r<=j; r++)
                {
                    int t=e[i][r - 1] + e[r + 1][j] + w[i][j];
                    if (t < e[i][j])
                        e[i][j] = t;
                }
            }
        printf("%d\n", e[1][n]);
    }
    return 0;
}