题解：P4539 [SCOI2006] zh_tree

· · 题解

模拟赛题，只推了一点式子，忘记了区间背包和中序遍历的关系，然后部分分也挂了，所以得了 0 分。

以下内容有点参考课件。

观察到根节点深度为 0，而下面的式子又为 k(r+1)+c，r 加了一，于是我们考虑默认根节点深度为 1，因为这俩是等价的。

首先看到式子 \sum\limits_{i = 1}^n h_if_i，好像没啥入手点，于是我们把它拆出来：

\begin{align}\sum\limits_{i = 1}^n h_i f_i & = \sum\limits_{i = 1}^n \frac{\left(kr_i+c\right)d_i}{S} & \notag\\ & = \sum\limits_{i = 1}^n \frac{kr_id_i}{S} + \sum\limits_{i = 1}^n \frac{cd_i}{S}\notag\\&=\frac{k}{S}\sum\limits_{i=1}^n r_id_i + \frac{c}{S}\sum\limits_{i=1}^n d_i\notag\end{align}

因为 \sum\limits_{i = 1}^n d_i = S，所以：

\begin{align}\frac{k}{S}\sum\limits_{i=1}^n r_id_i + \frac{c}{S}\sum\limits_{i=1}^n d_i = \frac{k}{S}\sum\limits_{i=1}^n r_id_i + c\notag\end{align}

因为 k，S 非负，所以问题转化为求 \sum\limits_{i=1}^n r_id_i 的最小值，我们既做价值。

于是我们设 f_{dep,i ,j} 为节点 [i ,j] 构成的中序遍历为 [i\dots j] 的根节点深度为 dep 的最小价值，发现中序遍历这玩意儿和区间 DP 类似，从这题可知，蒟蒻不作解释：

f_{dep ,i ,j} = \min\limits_{k = i}^j \{f_{dep + 1 ,i ,k - 1} + f_{dep + 1 ,k + 1 ,j} + d_kdep\}

细节：

时间复杂度为 \mathcal O(n^4)，在普通区间 DP 的基础上增加了枚举 dep 的时间复杂度，这题可以通过，但是我模拟赛不能通过。

那么我们能不能删除 dep 这一维呢？

是可以的，我们可以只计算当前子树的价值。

我们设 f_{i ,j} 为节点 [i ,j] 构成的中序遍历为 [i\dots j] 的根节点深度为 dep 的最小价值。

先看一下转移：

f_{i ,j} = \min\limits_{k = i}^j \{f_{i ,k - 1} + f_{k + 1 ,j} + \sum\limits_{p = i}^j d_p\}

注意到后面的 \sum\limits_{p = i}^j d_p，我们发现它计算了新的贡献。

可以看图解：

假设我们一开始知道如下两个子树的价值总和：

然后我们让 k 为它们的根，那么 k 的子树的所有节点对价值的贡献都会加一，因为它们的深度都增加了 1：

这样答案是 f_{1 ,n}\times \frac{k}{S} + c，且对于边界一个节点也不会出错。

总时间复杂度为 \mathcal O(n^3)，可以通过。

# include <bits/stdc++.h>

# define int long long
# define up(i, x, y) for (int i = x; i <= y; i++)
# define dn(i, x, y) for (int i = x; i >= y; i--)
# define inf 1e18

using namespace std;

inline int read(){int x = 0, f = 0;char ch = getchar();while (!isdigit(ch)) {f |= (ch == '-');ch = getchar();}while (isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();return f ? -x : x;}
inline void write(int x){if (x < 0)putchar('-'), x = -x;if (x > 9)write(x / 10);putchar(x % 10 | 48);}
inline void writeln(int x){write(x), putchar('\n');}
inline void writesp(int x){write(x), putchar(' ');}

const int N = 305;
int n;
double k ,c ,d[N];
double f[N][N];

namespace lolcrying {    
    signed main () {    
        n = read () ; cin >> k >> c;
        double sum = 0;
        up (i ,1 ,n) cin >> d[i] ,sum += d[i];
        up (i ,1 ,n) up (j ,1 ,n) f[i][j] = inf;
        up (i ,1 ,n) f[i][i - 1] = 0 ,d[i] += d[i - 1];
        up (len ,1 ,n) {//其实 f[i][i] 可以不初始化，也可以直接放到 DP 里，计算一下还是 d[i]（这里指的不是前缀和的 d[i]）。
            up (i ,1 ,n - len + 1) {
                int j = i + len - 1;
                up (k ,i ,j) f[i][j] = min (f[i][j] ,f[i][k - 1] + f[k + 1][j]);//枚举根节点 k。
                f[i][j] += d[j] - d[i - 1];//前缀和，写不写无所谓。
            }
        } printf ("%.3lf\n" ,(f[1][n] * k / sum + c));
        return 0;
    }
}
signed main () {
    int T = 1;
    while (T --) lolcrying :: main ();
    return 0;
}