POJ 1784 - Huffman's Greed

http://poj.org/problem?id=1784

概要

\(n\) 個の値 \(K_1, \cdots, K_n (K_1 < \cdots < K_n)\) に対する二分探索木を考える。 \(p_i\) を \(K_i\) の値が探される確率、\(q_i\) を \(K_i\) より大きく \(K_{i+1}\) より小さい値が探される確率とする。 ここで \(q_0\) は \(K_1\) より小さい値が探される確率、\(q_n\) は \(K_n\) より大きい値が探される確率とする。

このとき、コストが最小となる二分探索木のコストを答える。 コストは \(\Sigma_{i=1 \ldots n} p_i \cdot (1 + \mathit{level}(K_i)) + \Sigma_{i=0 \ldots n} q_i \cdot \mathit{levelbetween}(K_i, K_{i+1})\) で計算する。 level はそのノードの深さ (ルートの深さを 0 とする) であり、levelbetween はその間の葉ノードの深さである。

制約

• \(1 \le n \le 200\)
• \(1 \le \Sigma_{i=1 \ldots n} p_i + \Sigma_{i=0 \ldots n} q_i \le 10 ^ 6\)

解法

dp[i][j] = K_i から K_j までの区間で作る二分探索木の最小コスト

という DP。 区間の大きさ d を大きくしながら

dp[i][i+d] = min { dp[i][k] + dp[k+1][i+d] + (新たに K_k をルートとする二分探索木を作ることで level が1つ上がって生じる q_i + p_i + … + q_k + q_{k+1} + p_{k+1} + … + q_j)

と更新していく。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF && N != 0) {
 9     static int p[201], q[201];
10     for (int i = 1; i <= N; i++) {
11       scanf("%d", &p[i]);
12     }
13     for (int i = 0; i <= N; i++) {
14       scanf("%d", &q[i]);
15     }
16 
17     static int sums[202];
18     for (int i = 0; i <= N; i++) {
19       sums[i+1] = p[i] + q[i] + sums[i];
20     }
21     static int dp[201][201];
22     for (int i = 0; i <= N; i++) {
23       fill_n(dp[i], N+1, 100000000);
24       dp[i][i] = 0;
25     }
26     for (int d = 1; d <= N; d++) {
27       for (int i = 0; i+d <= N; i++) {
28         const int j = i + d;
29         for (int k = i; k+1 <= j; k++) {
30           dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sums[j+1] - sums[i] - p[i]);
31         }
32       }
33     }
34     printf("%d\n", dp[0][N]);
35   }
36   return 0;
37 }