UVA - 10304 Optimal Binary Search Tree

本文主要是介绍UVA - 10304 Optimal Binary Search Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给定一个序列 S= (e₁, e₂, ..., e_n)， 将这些序列构成一个二叉搜索树，要求按深度*频率的总权值最小，根节点深度为0，跟矩阵连乘相似，显然这题具有最优子结构，所以我们假设dp[i][j]表示从(i,j)构成的搜索树最小是多少，然后便模仿矩阵连乘的思路，枚举每一个点作为根节点，接着就是确定状态转移方程了，当我们确定k为节点的时候，那么序列（k1,...,k-1）作为左子树的深度加1，右子树同样如此，那么dp[i][j] = dp[i][k-1]+dp[k+1][j] + sum[i][j] - b[k],sum[i][j]代表（i,j）的频率和，自己想一下，这样递归算下去，就是深度*频率了。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 256;int n;
int b[MAXN],sum[MAXN],dp[MAXN][MAXN];int main(){while (scanf("%d",&n) != EOF){sum[0] = 0;for (int i = 1; i <= n; i++){scanf("%d",&b[i]);sum[i] = sum[i-1] + b[i];}memset(dp,0,sizeof(dp));for (int d = 2; d <= n; d++){for (int l = 1; l + d -1 <= n; l++){int r = l + d -1;int ans = 1<<29,tot = sum[r] - sum[l-1];for (int k = l; k <= r; k++)ans = min(ans,dp[l][k-1]+dp[k+1][r]+tot-b[k]);dp[l][r] = ans;}}printf("%d\n",dp[1][n]);}return 0;
}

这篇关于UVA - 10304 Optimal Binary Search Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---