题解

思路

设 $g_i$ 为从城市 $i-1$ 首次到达城市 $i$ 所需天数的期望。由一步转移可得

$$g_1=1,\qquad g_i=1+\frac{a_{i-1}}{a_i}(g_{i-1}+1).$$

归纳得到

$$g_i=1+2\frac{a_1+\cdots+a_{i-1}}{a_i}.$$

因此总期望为

$$n+2\sum_{i=2}^n\frac{s_{i-1}}{a_i},\qquad s_i=\sum_{j=1}^i a_j.$$

额外预算放到最后一条边不会使答案变差，所以最优解满足 $s_n=m$。

定义 $dp[i][s]$ 为前 $i$ 条边美丽值之和为 $s$ 时，上式分数部分的最小值。转移为

$$dp[i][s]=\min_{i-1\le k<s}\left(dp[i-1][k]+\frac{k}{s-k}\right).$$

做法

小范围可以枚举 $m$ 的全部正整数拆分。直接枚举转移得到 $O(nm^2)$ 算法。

代价函数 $w(k,s)=k/(s-k)$ 满足决策单调性：同一层中，最优决策随 $s$ 单调不减。于是每层用分治计算一段状态，并把最优决策区间传给两个子问题，将复杂度降为 $O(nm\log m)$。

最终答案为 $n+2dp[n][m]$。使用 long double 计算并输出足够多的小数位。

复杂度

• 枚举正整数拆分为指数复杂度。
• 直接动态规划为 $O(nm^2)$ 时间、$O(m)$ 空间。
• 分治优化为 $O(nm\log m)$ 时间、$O(m)$ 空间。