当前位置:编程学习 > C/C++ >>

uva 10304 - Optimal Binary Search Tree(区间dp)

题目大意:给出n个词语的出现频率(从小到达排列),要根据这些词语的出现频率建一个类似于哈夫曼编码的最优树, 不过不同的是这棵数的每个节点都应该优值,并且对于每个节点来说,左边所有的节点上的值(词语的频率)都要小于该节点, 右边的则都要大于。然后根据节点的层数*节点值, 输出最小的编码值。
 
解题思路:问题可以看成是一个区间dp的问题, 可问题的关键是怎么确定节点的层数,想了很久才发现,根本不用靠靠层数,只要逐层递加就可以了。
 
 
#include <stdio.h>  
#include <string.h>  
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;  
}  

 


补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,