P4539

一个区间 DP 的较为简单的题目。

1. 题意

• 要求构造一个大小为 $n$ 的二叉树，按照中序遍历标号为 $1\sim n$，然后给定每个编号的频率 $f_i$，并且给定常数 $k,c$ 为实数，请最小化（设根节点深度为 1）：

$$\sum_{i=1}^nf_i\times(k\times dep_i+c)$$

• $n\leq30,\sum f_i=1,0<k,c\leq100$

2. 思路

其实可能很多同学（其实就是我）都会想到 Huffman Tree，它是基于一个贪心的想法，但是我们可以比较一下两个的式子。

$$\sum_{i=1}^nf_i\times dep_i$$ $$\sum_{i=1}f_i\times(k\times dep_i+c)$$

这两个其实是有一定区别的。

本题中，不同节点是一定会出现祖先关系，并且只有 $n$ 个节点。但是 Huffman Tree 却要求给定的 $n$ 个节点不能出现祖先关系，构造出来后，也会超过 $n$ 个节点。

那本题怎么做呢？

首先，我们可以发现一个性质：假设当前子树覆盖的区间为 $[l,r]$，根节点为 $t$，那么左边的子树覆盖的区间为 $[l,t-1]$，右边的子树为 $[t+1,r]$。

这就是一个典型的区间 DP 了。

当我们要计算 $dp(l,r)$ 的时候，我们直接枚举根节点 $t$，然后递归计算 $dp(l,t-1)$ 和 $dp(t+1,r)$，然后我们将左右子树直接接在 $t$ 这个节点上。

怎么计算贡献呢？其实很简单，我们左右的子树的深度都要加一，对于整个的贡献就是 $k\times (s(r)-s(l-1)-f(t))$，其中 $s(i)=\sum_{j=1}^if(j)$。

再加上 $t$ 的贡献，那么，我们就可以得到式子：

$$dp(l,r)=\min_{t\in[l,r]}\{dp(l,t-1)+dp(t+1,r)+k\times(s(r)-s(l-1))+c\times f(t) \}$$

时间复杂度为 $O(n^3)$，轻松通过。

3. 代码

采用的递归式写法。

double solve(int l, int r)
{
	if (l > r) return 0;
	if (l == r) return (k + c) * fru[l];
	double &v = f[l][r];
	if (v >= 0) return v;
	v = INF;
	for (int mid = l; mid <= r; ++ mid)
		v = min(v, solve(l, mid - 1) + k * (s[r] - s[l - 1]) + c * fru[mid] + solve(mid + 1, r));
	return v;
}