牛客OI周赛D-Talk(期望dp)

很容易想到定义$dp[i]$是已经执行了前$i$个事件,还期望讲多久结束

$dp[i]=p[i]\ast (dp[i+1]+1)+(1-p[i])\ast (dp[i-1]+1)$

发现这个式子前后都有依赖,可以高斯消元,但这题似乎卡这个精度

$我们这么定义dp[i]$为执行前$i$个事件期望多久

$$dp[i]=dp[i-1]+1+(1-p[i-1])\ast (dp[i]-dp[i-2])$$

是不是很迷~

$dp[i-1]+1$很好理解,就是继承前面的状态,且拿出一次机会来执行第$i$件事

$有p[i-1]概率成功,从i-1转移到i,此时不需要额外的花费$

$有1-p[i-1]概率失败,从i-1掉到了i-2$

$那么现在需要从i-2转移到i$

$也就是需要从i-2转移到i-1,花费dp[i-1]-dp[i-2]$

$从i-1转移到i,花费dp[i]-dp[i-1]$

$相加花费得到上面的式子$

对$dp[i]$移项可以得到

$$dp[i]=\frac{dp[i-1]+1-(1-p[i-1])\ast dp[i-2]}{p[i-1]}$$

最后$dp[n+1]$即位答案

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int n; double dp[maxn],p[maxn]; int main() { cin >> n; for(int i=1;i<=n;i++) cin >> p[i]; dp[0]=dp[1]=0; for( int i=2;i<=n+1;i++ ) dp[i] = ( dp[i-1]+1.0-( 1.0-p[i-1] )*dp[i-2] )/p[i-1]; printf("%.3lf",dp[n+1]); }