首页 > ACM题库 > UVA > UVA-10304-Optimal Binary Search Tree[区间DP]
2014
01-20

UVA-10304-Optimal Binary Search Tree[区间DP]

Optimal Binary Search Tree

Given a set S = (e1, e2, …, en) of n distinct elements such that e1 < e2 < … < en and considering a binary search tree (see the previous problem) of the elements of S, it is desired that higher the query frequency of an element, closer will it be to the root.

The cost of accessing an element ei of S in a tree (cost(ei)) is equal to the number of edges in the path that connects the root with the node that contains the element. Given the query frequencies of the elements of S(f(e1), f(e2, …, f(en)), we say that the total cost of a tree is the following summation:

f(e1)*cost(e1) + f(e2)*cost(e2) + … + f(en)*cost(en)

In this manner, the tree with the lowest total cost is the one with the best representation for searching elements of S. Because of this, it is called the Optimal Binary Search Tree.

Input

The input will contain several instances, one per line.

Each line will start with a number 1 <= n <= 250, indicating the size of S. Following n, in the same line, there will be n non-negative integers representing the query frequencies of the elements of S: f(e1), f(e2), …, f(en). 0 <= f(ei) <= 100.  Input is terminated by end of file.

Output

For each instance of the input, you must print a line in the output with the total cost of the Optimal Binary Search Tree.

 

Sample Input

1 5
3 10 10 10
3 5 10 20

 

Sample Output

0
20
20

题意

给一个序列即可 S = (e1,e2,…,en),且e1<e2<..<en.要把这些序列构成一个二叉搜索树。
二叉搜索树是具有递归性质的,且若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它
的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
因为在实际应用中,被访问频率越高的元素,就应该越接近根节点,这样才能更加节省查找时间。
每个元素有一个访问频率f(ei),当元素位于深度为k的地方,那么花费cost(ei) = k.
所有节点的花费和访问频率乘积之和为:
sum = f(e1)*cost(e1) + f(e2)*cost(e2) + … + f(en)*cost(en)
我们叫sum值最小的二叉搜索树为最优二叉搜索树。
按顺序给出集合序列S,和每个元素的频率f(ei),求sum的最小值

思路

因为他题目给的序列是从小到大的,那么对于这个序列的任意一个ei,设ei为根节点,
我们可以知道在序列中ei左边的所有数会构成ei的左子树,ei的右边的所有数会构成
ei的右子树。
那么我们就可以枚举根节点,然后选择值最小的一种方案。
说到这里,再结合题目的数据范围,那么很容易可以想到就是区间dp了!

设f(i, j)表示序列区间(i, j)的数构成的一棵最优二叉查找树的值,
当枚举根节点ek时,它的左子树(wi,wi+1,..,wk-1)的所有节点的深度都会增加1,
那么左子树增加sum(w1,w2,…wk-1)
右子树(ek+1, ek+2,..ej)的值也会增加sum(ek+1,ek+2,…,ej).
可以看出,那么总共会增加sum(i, j) – wk

那么就可以推出状态转移了:
f(i, j) = min{ f(i,k-1)+f(k+1,j)+sum(i, j) – wk | i<=k<=j}

/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source      : uva-10304 Optimal Binary Search Tree
 *   @description : 区间dp
 *   @author      : shuangde
 *   @blog        : blog.csdn.net/shuangde800
 *   @email       : [email protected]
 *   Copyright (C) 2013/09/06 16:37 All rights reserved. 
 *======================================================*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long int64;
const double PI  = acos(-1.0);
const int INF = 0x3f3f3f3f;

const int MAXN = 210;
int n;
int w[MAXN];
int sum[MAXN];
int f[MAXN][MAXN];

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;
}

 

 


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 样例输出和程序输出不吻合,修改一下样例输出吧。我用的是VC编译器,会提示我的i和j变量重复定义

  3. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢