JZOJ 3248 Type

考虑倒序 DP，设 $f_i$ 表示从第 $i$ 位输入到结尾的最小期望时间。

转移则考虑枚举下一次在何处检查，有

$$\begin{array}{rl}{f}_i& =\underset{i\le j\le n}{min}\left\{t+j-i+1+\sum _{k=i}^j\left(\prod _{l=i}^{k-1}(1-p_l)\right)p_k(f_k+j-k+1)+\left(\prod _{l=i}^j(1-p_l)\right)f_{j+1}\right\}\\ & =\frac{1}{1-p_i}\underset{i\le j\le n}{min}\left\{t+(1+p_i)(j-i+1)+\sum _{k=i+1}^j\left(\prod _{l=i}^{k-1}(1-p_l)\right)p_k(f_k+j-k+1)+\left(\prod _{l=i}^j(1-p_l)\right)f_{j+1}\right\}\end{array}$$

然后 $O(n^2)$ 也不难做，只要每次维护一下转移值的增加量即可。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3e3;
int n,t;
double a[N + 5],f[N + 5];
int main()
{
    scanf("%d%d",&n,&t);
    for(register int i = 1;i <= n;++i)
        scanf("%lf",a + i),f[i] = 1e18;
    for(register int i = n;i;--i)
    {
        double cur = 0,prod = 1,sum = a[i];
        for(register int j = i;j <= n;++j)
        {
            j > i && (sum += cur + prod * a[j] * (f[j] + 1));
            cur += prod * a[j],prod *= 1 - a[j];
            f[i] = min(f[i],(sum + prod * f[j + 1] + t + j - i + 1) / (1 - a[i]));
        }
    }
    printf("%.8f\n",f[1]);
}