Jellyfish and Miku
D<C<B,哈哈。
设 \(dp_i\) 为起点为 i 时的期望步数,则
\[dp_0=1+dp_1\\
dp_n=0\\
dp_i=1+\frac{a_{i-1}}{a_{i-1}+a_i}dp_{i-1}+\frac{a_{i-1}}{a_{i-1}+a_i}dp_{i+1}
\]
化简第三个式子可得
\[a_{i+1}(dp_i-dp_{i+1})=a_i(dp_{i-1}-dp_i)+a_i+a_{i+1}
\]
设 \(f_i=dp_{i}-dp_{i+1}\),则
\[a_{i+1}f_i=a_{i}f_{i-1}+a_i+a_{i+1}\\
f_i=1+\frac{a_i}{a_{i+1}}(1+f_{i-1})
\]
将 \(f_0=1\) 代入可得
\[f_i=\frac{2\sum_{j=1}^{i-1}a_j}{a_i}+1
\]
你也可以在开头保留 \(dp_{i-1}\) 和 \(dp_{i}\) 得到一样的式子。
那么 a 不降,时间复杂度 \(\Omicron(nm\log n)\)。
#include<cstdio>
#include<iostream>
using namespace std;
#define db double
const int MAXN=3005;
const int INF=0x3f3f3f3f;
int n,m;
db dp[MAXN][MAXN];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=INF;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int k=1;j+k*(n-i)<=m;k++){
dp[i+1][j+k]=min(dp[i+1][j+k],dp[i][j]+1.0*j/k);
}
}
}
printf("%.10lf\n",dp[n][m]*2+n);
return 0;
}