uva 10304 Optimal Binary Search Tree(dp)

Optimal Binary Search Tree
Input: standard input
Output: standard output
Time Limit: 30 seconds
Memory Limit: 32 MB
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 eiof 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 

(The Joint Effort Contest, Problem setter: Rodrigo Malta Schmidt)
두 갈래로 나무의 성질을 검색하면 나무뿌리를 일일이 들기 쉽다. 그리고 나무뿌리보다 작은 것은 모두 왼쪽 나무에 놓고 나무뿌리보다 큰 것은 모두 오른쪽 나무에 있다. 왜냐하면 그들의 층수가 모두 1을 더하기 때문에 소비는 그것들의 합을 더하고 나머지는 좌우 나무의 가장 좋은 해답을 구하는 것이다. 구간dp.

#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<set>
#include<cmath>
using namespace std;
const int maxn = 1000 + 5;
const int INF = 1e9;
const double eps = 1e-6;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> P;
#define fi first
#define se second

int e[maxn];
int dp[maxn][maxn];
int sum[maxn];

int dfs(int l, int r){
    if(l >= r)
        return dp[l][r] = 0;
    if(dp[l][r] != -1)
        return dp[l][r];
    int ret = INF;
    ret = min(ret, dfs(l+1, r)+sum[r]-sum[l]);
    ret = min(ret, dfs(l, r-1)+sum[r-1]-sum[l-1]);
    for(int i = l+1;i <= r-1;i++){
        ret = min(ret, dfs(l, i-1)+sum[i-1]-sum[l-1]+dfs(i+1, r)+sum[r]-sum[i]);
    }
    return dp[l][r] = ret;
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        sum[0] = 0;
        for(int i = 1;i <= n;i++){
            scanf("%d", &e[i]);
            sum[i] = sum[i-1]+e[i];
        }
        memset(dp, -1, sizeof dp);

        printf("%d
", dfs(1, n));
    }
    return 0;
}