uva-10304 Optimal Binary Search Tree（區間dp）

  題目鏈接：uva-10304   題意    給一個序列即可 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;
}