JZOJ 3248.Type

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

转移则考虑枚举下一次在何处检查,有 \[ \begin{aligned} f_i &= \min\limits_{i \le j \le n}\left\{t + j - i + 1 + \sum\limits_{k=i}^j \left(\prod\limits_{l=i}^{k-1} (1-p_l)\right) p_k (f_k + j - k + 1) + \left(\prod\limits_{l=i}^j (1-p_l)\right) f_{j+1}\right\} \\ &= \frac 1{1-p_i}\min\limits_{i \le j \le n}\left\{t + (1+p_i)(j - i + 1) + \sum\limits_{k=i+1}^j \left(\prod\limits_{l=i}^{k-1} (1-p_l)\right) p_k (f_k + j - k + 1) + \left(\prod\limits_{l=i}^j (1-p_l)\right) f_{j+1}\right\} \end{aligned} \]

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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]);
}