uva10304 最优二叉排序树（四边形优化）

秒速五厘米 2021-12-14 02:19 272阅读 0赞

## 题意：给n个符号建立一棵排序二叉树，给出每个符号检索的频率，要求从检索的次数最小。   分析：《训练指南》P64。 ##

## 参考：[https://blog.csdn.net/count24/article/details/7226640][https_blog.csdn.net_count24_article_details_7226640] ##

## 代码： ##

#include<bits/stdc++.h>
    #define INF 16843009
    #define IM 253
    #define FU(i,a,b) for (int _n(b), i(a); i < _n; i++)
    #define FD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
    #define CL(a,v) memset((a),(v),sizeof(a))
    using namespace std;
    int n;
    int sum[IM];
    int w[IM][IM];
    
    int dp[IM][IM];
    int s[IM][IM];
    
    void Init(){
    	int t;
    	sum[0] = 0;
    	FU(i,1,n+1){
    		cin>>t;
    		sum[i] = sum[i-1] + t;
    	}
    	FU(i,0,n+1)
    		FU(j,i,n+1)
    			w[i][j] = sum[j] - sum[i-1];
    	CL(dp,1);
    }
    
    int DP(){
    	FU(i,0,IM) dp[i][i] = 0,s[i][i] = i;
    	FU(len,2,n+1){
    		FU(i,1,n+4){
    			int j = i + len - 1;
    			if(j > n+2) break;  // index !!!
    			FU(k,s[i][j-1],s[i+1][j]+1){
    				if(i > k-1) dp[i][k-1] = w[i][k-1] = 0;
    				if(k+1 > j) w[k+1][j] = dp[k+1][j] = 0;
    				int tmp = dp[i][k-1]+dp[k+1][j]+w[i][k-1]+w[k+1][j];
    				if(tmp < dp[i][j]){
    					dp[i][j] = tmp;
    					s[i][j] = k;
    				}
    			}
    		}
    	}
    	return dp[1][n];
    }
    
    int main(){
        while(cin>>n){
        	Init();
        	cout<<DP()<<endl;
        }
        return 0;
    }

[https_blog.csdn.net_count24_article_details_7226640]: https://blog.csdn.net/count24/article/details/7226640

发表评论取消回复

表情：

评论列表（有 0 条评论，272人围观）

还没有评论，来说两句吧...

相关阅读

相关查找二叉树、完全二叉树、线索二叉树、最优二叉树

文章目录前言一、查找二叉树（二叉排序树）二、完全二叉树三、线索二叉树四、最优二叉树（哈夫曼树） ----------------

痛定思痛。/ 2023年10月01日 21:38/ 0 赞/ 54 阅读

相关二叉树和排序二叉树

二叉树 > 相关名词 > > 根节点 > > 左叶子节点 > > 右叶子节点 > > 子树 > > 高度 > 二叉树的排序方式： > > 　　- 广度遍历（

灰太狼/ 2023年08月17日 16:53/ 0 赞/ 241 阅读

相关哈夫曼树(最优二叉树)

文章目录前言哈夫曼树(最优二叉树) 定义与原理树的路径长度

红太狼/ 2023年06月10日 11:28/ 0 赞/ 52 阅读

相关 1024 最优二叉搜索树

Description 给定N个整数关键字, 每个关键字有一搜索概率, 关键字外区间(共N+1个区间)也有搜索概率. 可根据关键字构造二叉搜索树来减少搜索代价

柔情只为你懂/ 2022年09月12日 00:57/ 0 赞/ 181 阅读

相关二叉树-详解二叉排序树

二叉搜索树首先二叉排序树也是一棵二叉树，所谓二叉树，就是“任何节点最多只允许两个子节点”，这两个子节点称为左右子节点。如下便是一个二叉树。 ![这里写图片描述][2

旧城等待，/ 2022年05月17日 01:18/ 0 赞/ 338 阅读

相关 uva10304 最优二叉排序树（四边形优化）

题意：给n个符号建立一棵排序二叉树，给出每个符号检索的频率，要求从检索的次数最小。分析：《训练指南》P64。参考：[https://blog.csdn.net/

秒速五厘米/ 2021年12月14日 02:19/ 0 赞/ 273 阅读

相关 uva10304 Optimal Binary Search Tree（最优二叉排序树区间dp）

题意：给n个符号建立一棵排序二叉树，给出每个符号检索的频率，要求从检索的次数最小。分析：《训练指南》P64，很详细。代码： include<bits

- 日理万妓/ 2021年12月13日 20:13/ 0 赞/ 220 阅读

相关最优二叉树-哈夫曼树（Haffman）

最优二叉树，也称为哈夫曼树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。设二叉树具有n个带权值的叶子结点,则从根结点到每一个叶子结点的路径长度与该

野性酷女/ 2021年09月18日 09:50/ 0 赞/ 463 阅读

相关最优二叉树——哈夫曼树

最优二叉树——哈夫曼树标签： [ struct][struct][null][][算法][Link 1][input][][path][][tree][] 2012-

ゝ一纸荒年。/ 2021年09月14日 05:04/ 0 赞/ 467 阅读

相关树之赫夫曼树最优二叉树

一、介绍赫夫曼树可以用来优化算法，减少运行次数；还可以用于电报编码。 ![这里写图片描述][20160905123647982] 二、优化算法对于我们嵌套

深碍√TFBOYSˉ_/ 2021年09月11日 01:44/ 0 赞/ 399 阅读