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++ ,