解題區/解題區 - UVa

UVa 12809 - Binary Search Tree

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

類似 UVa 10304 - Optimal Binary Search Tree，給每個節點的拜訪頻率，建造一個二元樹，使得詢問次數最小化。

Sample Input

1
2
3
4
5
6
3
0.33 0.34 0.33
3
0.8 0.15 0.05
4
0.23 0.4 0.17 0.2

Sample Output

1
2
3
1.6600
1.2500
1.7700

Solution

套用四邊形不等式進行優化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h> 
#include <string.h> 
double f[128];
double sum[128], w[128][128];
double dp[128][128];
int arg[128][128];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%lf", &f[i]);
        sum[0] = 0;
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + f[i];
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                w[i][j] = sum[j] - sum[i - 1];
        for (int i = 0; i <= n; i++)
            dp[i][i] = 0, arg[i][i] = i;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; i + j <= n; j++) {
                double mn = 1e+30;
                int idx = -1;
                for (int k = arg[j][i+j-1]; k <= arg[j+1][i+j]; k++) {
                    double t = dp[j][k-1] + dp[k+1][i+j] + w[j][k-1] + w[k+1][i+j];
                    if (t < mn)
                        mn = t, idx = k;
                }
                dp[j][i+j] = mn, arg[j][i+j] = idx;
            }
        }
        printf("%lf\n", dp[1][n] + 1);
    }
    return 0;
}