自动搬运

查看原文

来自洛谷，原作者为

	mqxmm 沐晴つ

搬运于2025-08-24 22:01:08，当前版本为作者最后更新于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;
}