Description
张老师根据自己工作的需要，设计了一种特殊的二叉搜索树。
他把这种二叉树起名为zh_tree，对于具有n个结点的zh_tree，其中序遍历恰好为(1，2，3，…，n)，其中数字1，2，3，…，n 是每个结点的编号。n个结点恰好对应于一组学术论文中出现的n个不同的单词。
第 (j) 个单词在该组论文中出现的次数记为 (j)，例如，(d_2~=~10) 表示第 (2) 个结点所对应的单词在该组论文中出现了 (10) 次。设该组论文中出现的单词总数为 (S) ，显然，(S~=~sum_{i = 1}^{n} d_i)。记 (f_i~=~frac{d_i}{s}) 为第j个单词在该组论文中出现的概率（频率）。
张老师把根结点深度规定为 (0) ，如果第 (j) 个结点的深度为 (r) ，则访问该结点 (j) 的代价 (h_j) 为 (h_j~=~k(r + 1)~+~c)，其中(k,c)为已知的不超过100的正常数。
则zh_tree是满足以下条件的一棵二叉树：(sum_{i = 1}^n f_i h_i) 达到最小。
我们称上式为访问zh_tree的平均代价。 请你根据已知数据为张老师设计一棵zh_tree。
Input
第1行：3个用空格隔开的正数： n k c 其中n<30，为整数，k，c为不超过100的正实数。 第2行：n个用空格隔开的正整数，为每个单词出现的次数(次数<200)。
Output
输出一行表示最小平均代价
Hint
(1~leq~n~leq~30~,~0~leq~d_i~leq~200)
Solution
其实就是推式子啦……
然后我们发现 (S~=~sum_{i = 1}^n d_i) 是个常数，(c) 也是一个常数，我们将只与这两个值有关的项从 (min) 中提出来
于是我们发现我们事实上要最小化 (sum_{i = 1}^n~(r_i~+~1)~d_i)，同时满足在这棵树上的中序遍历是 (1~sim~n)
由于中序遍历的顺序是“左中右”，所以我们可以直接设 (f_{l,r}) 为区间 ([l,r]) 的中序遍历为 (l~sim~r) 时上式的最小值，转移时可以枚举一个点 (i) 作为根，则左右子树显然要从上式最小的树形转移过来。转移时等价于左右子树每个点的树高都增加 (1)，即对答案的贡献增加 (sum_{j = l}^{i - 1} d_j~+~sum_{j = i + 1}^{r} d_j)。然后加上根的贡献 (d_i)，所以增加的贡献即为 (sum_{j = l}^r d_j)。直接使用前缀和优化该式子即可。
最后计算答案时记得将常数项乘上。复杂度 (O(n^3))。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif
#define rg register
#define ci const int
#define cl const long long
typedef long long int ll;
namespace IPT {
const int L = 1000000;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) {
end = buf + fread(front = buf, 1, L, stdin);
if (front == end) return -1;
}
return *(front++);
}
}
template <typename T>
inline void qr(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
if (lst == '-') x = -x;
}
template <typename T>
inline void ReadDb(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();
if (ch == '.') {
ch = IPT::GetChar();
double base = 1;
while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();
}
if (lst == '-') x = -x;
}
namespace OPT {
char buf[120];
}
template <typename T>
inline void qw(T x, const char aft, const bool pt) {
if (x < 0) {x = -x, putchar('-');}
rg int top=0;
do {OPT::buf[++top] = x % 10 + '0';} while (x /= 10);
while (top) putchar(OPT::buf[top--]);
if (pt) putchar(aft);
}
const int maxn = 35;
int n;
double c, k;
double MU[maxn], frog[maxn][maxn], sum[maxn];
int main() {
freopen("1.in", "r", stdin);
qr(n); ReadDb(k); ReadDb(c);
memset(frog, 127, sizeof frog);
for (rg int i = 1; i <= n; ++i) {
ReadDb(sum[i]);
frog[i][i] = sum[i]; frog[i + 1][i] = 0;
sum[i] += sum[i - 1];
}
frog[1][0] = 0;
for (rg int len = 1; len < n; ++len) {
for (rg int l = 1; l < n; ++l) {
int r = l + len;
if (r > n) break;
for (rg int i = l; i <= r; ++i) frog[l][r] = std::min(frog[l][r], frog[l][i - 1] + frog[i + 1][r]);
frog[l][r] += sum[r] - sum[l - 1];
}
}
printf("%.3lf
", (k * frog[1][n] + sum[n] * c) / sum[n]);
}
Summary
二叉树的中序遍历是 左中右 不是 中左右！