最优二叉搜索树HYSBZ - 3229 石子合并
目录
一，拓展二叉搜索树、搜索全域
1，空指针数目
一颗二叉搜索树，每个节点有2个指针，要么指向左右孩子，要么为空指针。
每个节点的空指针的数目为0-2
显然，所有空指针的数目总和为n+1
2，拓展节点、拓展二叉搜索树
如果把原树的n+1个空指针，都换成指向一个新增的叶子节点的指针，那么我们就会得到一颗新的树。
这颗新树有n个节点都有2个孩子，还有n+1个节点都是叶子节点，所以它是一颗Full Binary Tree
我们把这n+1个新节点叫做拓展节点，把这颗新树叫做拓展二叉搜索时。
3，拓展二叉搜索树的中序遍历
拓展二叉搜索树的中序遍历结果中，id为偶数的一定是n+1个拓展节点，id为奇数的一定是n个原有节点。
4，搜索全域
二叉树是物理概念，而二叉搜索树只是在二叉树的基础之上添加了逻辑概念，并没有添加物理概念。
任何一颗二叉树，按照中序遍历的结果，给各节点按照增序的方式进行赋值，都会得到一颗二叉搜索树。
类似的，我们给每个拓展节点赋予含义，让他们表示全域被n个值隔开的n+1个区间，那么它就能覆盖整个搜索的全域。
于是，拓展二叉搜索树便成为我们研究二叉搜索树的一个有力工具。
二，二叉搜索树的查找时间均值
设二叉搜索树n个节点的命中概率分别为p1...pn，n+1个拓展节点的命中概率分别为q0...qn，则∑pi + ∑qi = 1
二叉搜索树的平均查找时间为T = ∑pi*di + ∑qi*di，其中d是各个节点的搜索长度，即节点深度
三，最优二叉搜索树
给定n个节点，pi和qi都是已知的，构造一棵二叉搜索树，使得T = ∑pi*di + ∑qi*di取到最小值，称这样的二叉搜索树为最优二叉搜索树。
这个目标比较复杂，我不是很了解，不知道有没有这方面的算法。
四，最优纯拓展二叉搜索树
如果所有的pi都是0，也就是说我们只关心叶子节点，这样的二叉搜索树我们称之为纯拓展二叉搜索树。
给定pi=0，给定qi的情况下，使得T最小的二叉搜索树，我们称之为最优纯拓展二叉搜索树。
体现在石子归并问题中，如果石子是无序的，那就是构建最优二叉树，如果石子是有序的一排，那就是最优纯拓展二叉搜索树。
最优二叉树其实是贪心的，而最优纯拓展二叉搜索树是动态规划的。
五，加西亚-瓦克斯算法
构建最优纯拓展二叉搜索树，如果用区间DP，那就是O（n^2）的时间复杂度。
加西亚-瓦克斯算法是专门用来解决最优纯拓展二叉搜索树问题的，时间效率和快速排序类似，最坏情况是n^2，但是一般情况下很快
六，OJ实战
HYSBZ - 3229 石子合并
题目：
Description
在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将N堆石子合并成一堆的最小得分。
Input
第一行是一个数N。
以下N行每行一个数A，表示石子数目。
Output
共一个数，即N堆石子合并成一堆的最小得分。
Sample Input
4
1
1
1
1
Sample Output
8
HINT
对于 100% 的数据，1≤N≤40000
对于 100% 的数据，1≤A≤200
思路：
先从序列中找第一个st【k】使得st【k-1】<=st【k+1】然后合并st【k-1】与st【k】；
再从序列中从k往前找第一个st【j】使得st【j】>st【k-1】+st【k】然后将这个合并后的数放在j位置后；
如果找不到这样的j就把合并后的数放在最前面
如果找不到这样的k就合并最后2个数（因为这是最小的2个数）
如此往复直到只剩一堆；
代码：
-
#include<iostream>
-
#include<stdio.h>
-
using namespace std;
-
-
int main()
-
{
-
int n, low = 1, list[40005];
-
long long ans = 0;
-
scanf("%d", &n);
-
for (int i = 1; i <= n; i++)scanf("%d", &list[i]);
-
while (low < n - 1)
-
{
-
int i;
-
for (i = low; i < n - 1; i++)if (list[i] <= list[i + 2])
-
{
-
list[i + 1] += list[i], ans += list[i + 1];
-
for (int j = i; j > low; j--)list[j] = list[j - 1];
-
low++;
-
int j = i + 1;
-
while (list[j] > list[j - 1] && j > low)
-
{
-
list[j] ^= list[j - 1] ^= list[j] ^= list[j - 1];
-
j--;
-
}
-
break;
-
}
-
if (i == n - 1)
-
{
-
list[n - 1] += list[n];
-
ans += list[--n];
-
}
-
}
-
if (low == n - 1)ans += list[n - 1] + list[n];
-
cout << ans;
-
return 0;
-
}
-
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/114504382
- 点赞
- 收藏
- 关注作者
评论（0）