uva 10304 - Optimal Binary Search Tree(区间dp） - c++编程基础

题目大意：给出n个词语的出现频率（从小到达排列），要根据这些词语的出现频率建一个类似于哈夫曼编码的最优树，不过不同的是这棵数的每个节点都应该优值，并且对于每个节点来说，左边所有的节点上的值（词语的频率）都要小于该节点，右边的则都要大于。然后根据节点的层数*节点值，输出最小的编码值。

解题思路：问题可以看成是一个区间dp的问题，可问题的关键是怎么确定节点的层数，想了很久才发现，根本不用靠靠层数，只要逐层递加就可以了。

#include   
#include   
const int N = 300;  
const int MAX = 1 << 30;  
int min(int a, int b) { return a > b   b : a; }  
int n, dp[N][N], sum[N], num[N];  
  
void read() {  
    sum[0] = 0;  
    for (int i = 1; i <= n; i++) {  
        scanf("%d", &num[i]);  
        sum[i] = sum[i - 1] + num[i];  
    }  
}  
  
int solve() {  
    memset(dp, 0, sizeof(dp));  
    for (int i = 2; i <= n; i++) {  
        for (int j = i - 1; j; j--) {  
            dp[j][i] = MAX;  
            for (int k = j; k <= i; k++) {  
                dp[j][i] = min(dp[j][i], dp[j][k - 1] + dp[k + 1][i] + sum[i] - sum[j - 1] - num[k]);  
            }  
        }  
    }  
    return dp[1][n];  
}  
  
int main() {  
    while (scanf("%d", &n) == 1) {  
        read();  
        printf("%d\n", solve());  
    }  
    return 0;  
}