程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 小白dp uva 10304 - Optimal Binary Search Tree

小白dp uva 10304 - Optimal Binary Search Tree

編輯：C++入門知識

10304 - Optimal Binary Search Tree

Problem E

Optimal Binary Search Tree

Input: standard input

Output: standard output

Time Limit: 30 seconds

Memory Limit: 32 MB

Given a set S = (e₁, e₂, ..., e_n) of n distinct elements such that e₁ < e₂ < ... < e_n 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 e_i of S in a tree (cost(e_i)) 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(e₁), f(e₂, ..., f(e_n)), we say that the total cost of a tree is the following summation:

f(e₁)*cost(e₁) + f(e₂)*cost(e₂) + ... + f(e_n)*cost(e_n)

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(e₁), f(e₂), ..., f(e_n). 0 <= f(e_i) <= 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

題意：

給你一個序列，構造出一棵最優查找樹，輸出權值。

思路：

開始想的為三維dp，左、右、層數，寫了果斷TLE，沒想到怎麼改進，看了題解恍然大悟。

其實第三維可以去掉，因為每加一層，在加之前就能統計額外所加的權值了，就是兩個區間的總和，而不需要每層只算自己的。

感想：

有些時候真的自己怎麼想也想不到，看一下題解馬上就知道怎麼做了，每次都差那麼一點點，何時才能做到不看題解做出來呀。

每個題要能看出，每一步真正的改變了什麼，然後再想怎麼去處理。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 305
#define MAXN 100005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 0.000001
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int a[maxn],sum[maxn];
int dp[maxn][maxn];

int dfs(int le,int ri)
{
    if(le>ri) return 0;
    if(dp[le][ri]!=INF) return dp[le][ri];
    int i,j,t,best=INF;
    for(i=le;i<=ri;i++)
    {
        best=min(best,dfs(le,i-1)+dfs(i+1,ri)+sum[i-1]-sum[le-1]+sum[ri]-sum[i]);
    }
    dp[le][ri]=best;
    return best;
}
int main()
{
    int i,j,t;
    while(~scanf("%d",&n))
    {
        sum[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        memset(dp,0x3f,sizeof(dp));
        dfs(1,n);
        printf("%d\n",dp[1][n]);
    }
    return 0;
}
/*
1 5
3 10 10 10
3 5 10 20
*/