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