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

本文主要是介绍uva10304 Optimal Binary Search Tree（最优二叉排序树 区间dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

代码：

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 210;
int n;
int w[N];
int sum[N];
int f[N][N];int main(){while (~scanf("%d", &n)) {sum[0] = 0;for (int i = 1; i <= n; ++i) {scanf("%d", &w[i]);sum[i] = sum[i-1] + w[i];}memset(f, 0, sizeof(f));for (int d = 2; d <= n; ++d) {for (int l = 1; l + d - 1 <= n; ++l) {int r = l + d - 1;int ans = INF, tot = sum[r] - sum[l-1];for (int k = l; k <= r; ++k)ans = min(ans, f[l][k-1] + f[k+1][r] + tot - w[k]);f[l][r] = ans;}}printf("%d\n", f[1][n]);}return 0;
}

 

这篇关于uva10304 Optimal Binary Search Tree（最优二叉排序树 区间dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---