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

题意

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

思路

ei的右子树。

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]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
*======================================================*/
#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也帮想想, 有想法欢迎来邮件。谢谢