CF1874D题解

· · 题解

设 f_i 表示从 i 走到 n 需要的期望步数，则有：

\begin{cases}f_{0}=1+f_{1}\\f_{i}=1+\dfrac{a_i}{a_i+a_{i+1}}f_{i-1}+\dfrac{a_{i+1}}{a_i+a_{i+1}}f_{i+1}\quad(1\leq i<n)\\f_n=0\end{cases}

将第二条式子化简后得到：

a_{i+1}(f_{i}-f_{i+1})=a_i(f_{i-1}-f_{i})+a_i+a_{i+1}

设 g_{i}=f_{i-1}-f_{i}，则有：

\begin{cases}g_{1}=1\\a_{i+1}g_{i+1}=a_ig_i+a_i+a_{i+1}\end{cases}

可以计算得到：

g_{i}=2\times\frac{\sum\limits_{j<i}a_j}{a_i}+1

我们要求的答案就是 f_0：

\begin{aligned}f_0 & = \sum\limits_{i=1}^n (f_{i-1}-f_{i}) \\ & = \sum\limits_{i=1}^n g_{i} \\ & = \sum\limits_{i=1}^n (2\times\frac{\sum\limits_{j<i}a_j}{a_i}+1) \\ & = 2\times\sum\limits_{i=1}^n \dfrac{1}{a_i}(\sum\limits_{j=1}^{i-1}a_j)+n\end{aligned}

因此我们只需要最小化 \sum\limits_{i=1}^n \dfrac{1}{a_i}(\sum\limits_{j=1}^{i-1}a_j)。

设 dp_{i,s} 表示确定了 a_1,a_2,\cdots,a_i 的值， \sum\limits_{j=1}^{i}a_j=s 时，\sum\limits_{k=1}^i \dfrac{1}{a_k}(\sum\limits_{j=1}^{k-1}a_j) 的最小值。

有 dp_{i+1,s+k}\leftarrow dp_{i,s}\times \dfrac{s}{k}

这样的做法是 O(nm^2) 的。

我们发现，a 序列一定是不下降的。

证明:若存在 a_{i}>a_{i+1}，则交换 a_{i},a_{i+1} 后答案一定更优

所以我们得到上述转移方程的一个限制： s+k(n-i)\leq m。（后面至少能放下 n-i 个 k）

时间复杂度就变成了 O(m^2\log n)：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=3005;
int n,m;
double f[MAXN][MAXN];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i)
        for(int j=0; j<=m; ++j)
            f[i][j]=1e9;
    for(int j=0; j<n; ++j)
        for(int k=0; k<=m; ++k)
            for(int i=1; k+i*(n-j)<=m; ++i)
                f[j+1][k+i]=min(f[j+1][k+i],f[j][k]+k/(double)i);
    printf("%.15lf\n",f[n][m]*2+n);
    return 0;
}