首页 > 代码库 > 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;
}