首页 > 代码库 > UVA - 10304Optimal Binary Search Tree(递推)
UVA - 10304Optimal Binary Search Tree(递推)
题目:UVA - 10304Optimal Binary Search Tree(递推)
题目大意:给出一组数,e1 < e2 < ... < en,现在要求将这些数组成一棵二叉搜索树,并且使得sum (ei * cost(ei))最小。cost(ei)表示ei到到根节点之间有多少条边。
解题思路:首先二叉搜索树要满足左节点小于根节点,右节点大于根节点。因此对于e1 < e2 < ... < en这样一组数,我们只要枚举根节点的位置ek,将这个序列分成左右子树两部分(e1,e2..ek-1) (ek+ 1, ek + 2, ..en)。然后找到最优的根节点。而且对于两个子树,也是同样的做法(最优子结构)。
状态转移方程:dp【i】【j】 = MIN (dp【i】【k - 1】 + dp【k +1】【j】 + num【k - 1】 - num【i - 1】 + num【j】 - num【k】) 。
代码:
#include <cstdio> #include <cstring> const int N = 255; const int INF = 0x3f3f3f3f; int v[N]; int num[N]; int dp[N][N]; int n; int Min (const int a, const int b) { return a < b? a: b; } int main () { while (scanf ("%d", &n) != EOF) { num[0] = 0; for (int i = 1; i <= n; i++) { scanf ("%d", &v[i]); num[i] = num[i - 1] + v[i]; } for (int i = 1; i <= n; i++) dp[i][i] = 0; int left, right; for (int l = 1; l < n; l++) for (int i = 1; i + l <= n; i++) { dp[i][i + l] = INF; for (int j = i; j <= i + l; j++) { if (j != i) left = dp[i][j - 1] + num[j - 1] - num[i - 1]; else left = 0; if (j != i + l) right = dp[j + 1][i + l] + num[i + l] - num[j]; else right = 0; dp[i][i + l] = Min (dp[i][i + l], left + right); } } // printf ("%d %d\n", INF, 1<<30); printf ("%d\n", dp[1][n]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。