UVA Optimal Binary Search Tree(10304)

题目大意：

       给你n个点以及每个点的搜索频率，构建一个最优二叉树，使得二叉树的总权重最小，总权重等于每个点的搜索频率乘以其相应的深度的总和。设有3个点e1, e2, e3， 其搜索频率为f(e1), f(e2), f(e3)， 若构建的二叉树中，其三个点在树中的深度分别为h1, h2, h3，则 W =  f(e1) * h1 + f(e2) * h2 + f(e3) * h3。问题就是要求出最小的W。有点类似哈弗曼编码。

 

解题思路：

       动态规划，每次状态都假设只有三个点，即根节点，左子树和右子树，遍历计算出每个节点作为根节点时的最小权重。

       设 dp[L][H] 表示第 L 个节点到第 H 个节点构成最优二叉树的最小权重，则根节点遍历就是从 L 到 H 的范围内遍历。状态转移方程为：

                          ans = min( ans, dp[l][k-1] + dp[k+1][h] + sum[h] - sum[l-1] - v[k] );

方程中第 k 个节点为根节点，则dp[l][k-1] 表示从 l 到 k-1（即左子树）的最小权重， dp[k+1][h] 表示从 k+1 到h（即右子树）的最小权重，由于增加了一个根节点，则左右子树的深度都加 1 ， 所以要加上 l 到 h 内所有节点的搜索频率，由于根节点的深度为0， 所以最后要减去第 k 个节点的搜索频率v[k]。

         对于sum[h] 则表示从第 1 个节点到第 h 个节点的搜索频率总和，所以sum[h] - sum[l-1]表示 l 到 h 的所有节点的搜索频率总和。

 

代码：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

#define MAX 260

int sum[MAX];
int dp[MAX][MAX];

int main()
{
	int T, temp, h;

	while( cin>>T )
	{
		vector<int> v;
		memset( dp, 0, sizeof( dp ) );		
		memset( sum, 0, sizeof( sum ) );
		for( int i = 0; i < T; i++ )
		{
			cin>>temp;
			v.push_back(temp);
			sum[i] = sum[(i==0?0:i-1)] + temp;
		}

		for( int num = 1; num <= v.size(); num++ )  //表示处理几个节点
		{
			for( int l = 0; l + num < v.size(); l++ )  //l 表示处理的节点当中最小的那个节点， l + num 表示处理节点中最大的那个节点
			{
				h = l + num;
				int ans = 99999;
				for( int k = l; k <= h; k++ )  //从 l 到 h 中遍历所有节点作为根节点
				{
					ans = min( ans, dp[l][k-1] + dp[k+1][h] + sum[h] - sum[l-1] - v[k] );
				}
				dp[l][h] = ans;
			}
		}

		cout<<dp[0][v.size()-1]<<endl;
	}

	return 0;
}