题解「SCOI2006」zh_tree

mqxmm · 2020-12-15 19:49:20 · 题解

\texttt{Solution}

对于每个节点的深度 r_i，由于 h_i = k(r_i + 1) + c，不妨可以把根节点的深度改为 1，这样就可以直接用 现在的 r_i 表示 原来的 r_i + 1 了。

先把 \sum\limits_{i = 1}^n h_i f_i 化简：

\begin{aligned} \sum\limits_{i = 1}^n (h_i \times f_i) & = \sum\limits_{i = 1}^n (k \times r_i + c) \times \dfrac {d_i} S \\ & = \dfrac 1 S \times \sum\limits_{i = 1} ^{n} (k \times r_i + c) \times d_i \\ & = \dfrac 1 S \times \sum\limits_{i = 1}^n (k \times r_i \times d_i + c \times d_i) \\ & = \dfrac 1 S \times (\sum\limits_{i = 1}^n k \times r_i \times d_i + \sum\limits_{i = 1}^n c \times d_i) \\ & = (\dfrac 1 S \times \sum\limits_{i = 1}^n k \times r_i \times d_i) + (\dfrac 1 S \times c \times \sum\limits_{i = 1} ^{n} d_i) \\ & = (\dfrac k S \times \sum\limits_{i = 1}^n r_i \times d_i) + (\dfrac 1 S \times c \times S) \\ & = \dfrac {k \times \sum\limits_{i = 1}^n r_i \times d_i}{S} + c \\ \end{aligned}

题目要我们求 \sum\limits_{i = 1}^n h_i f_i 的最小值，就可以转化成求 \sum\limits_{i = 1}^n r_i \times d_i 的最小值。

状态定义：设 f_{L, R} 表示：一棵二叉树的 中序遍历(左子树，根节点，右子树) 为 L \sim R(L, L + 1, L + 2, \cdots, R) 时 \sum\limits_{i = L}^R r_i \times d_i 的最小值，最终的答案就是 \dfrac{k \times f_{1, n}}{S} + c。
初始化：\forall L = R = i, f_{L, R} = d_i；\forall L < R, f_{L, R} = + \infty。
状态转移：对于中序遍历为 L \sim R 的二叉树，枚举其根节点 tr(L \leq tr \leq R)，f_{L, R} = \min\limits_{tr = L}^R \{ f_{L, tr - 1} + f_{tr + 1, R} + \sum\limits_{i = L}^{R} d_i \} = \min\limits_{tr = L}^R \{ f_{L, tr - 1} + f_{tr + 1, R} \} + \sum\limits_{i = L}^{R} d_i。

如果需要输出方案，可以在转移过程中记录下 f_{L, R} 取最小值时的根节点，最后递归即可。

转移时 \sum\limits_{i = L}^{R} d_i 可以用前缀和作差，这样时间复杂度 O(n ^ 4) \to O(n ^ 3)，不过都可以 \texttt{AC}。

\texttt{code}

#include <cstdio>
#include <cstring>

#define Min(u, v) (((u) < (v)) ? (u) : (v))

const int MAX_n = 30;

int n, S;
int d[MAX_n + 5];
int zh[MAX_n + 5];

double k, c;
double dp[MAX_n + 5][MAX_n + 5];

int main()
{
    scanf("%d %lf %lf", &n, &k, &c);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &d[i]);
        zh[i] = (S += d[i]);
        dp[i][i] = 1.0 * d[i];
    }
    for (int L = 1; L + 1 <= n; L++)
        for (int R = L + 1; R <= n; R++)
            dp[L][R] = 1000000000.0;
    for (int Len = 2; Len <= n; Len++)
    {
        for (int L = 1, R = Len; R <= n; L++, R++)
        {
            for (int tr = L; tr <= R; tr++)
                dp[L][R] = Min(dp[L][R], dp[L][tr - 1] + dp[tr + 1][R]);
            dp[L][R] += 1.0 * (zh[R] - zh[L - 1]);
        }
    }
    printf("%.3lf\n", 1.0 * k * dp[1][n] / S + c);
    return 0;
}