JZOJ 3248 Type

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

转移则考虑枚举下一次在何处检查，有 fi=mini≤j≤n{t+j−i+1+j∑k=i(k−1∏l=i(1−pl))pk(fk+j−k+1)+(j∏l=i(1−pl))fj+1}=11−pimini≤j≤n{t+(1+pi)(j−i+1)+j∑k=i+1(k−1∏l=i(1−pl))pk(fk+j−k+1)+(j∏l=i(1−pl))fj+1}

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

代码：

#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]);
}