守卫者的挑战

期望dp。

记 $f(i,j,k)$ 表示考虑前 $i$ 场挑战，成功了 $j$ 次，剩余容量为 $k$ 的概率。$\mathcal O(n^2\sum a_i)$ 好像完全爆炸，但当 $k>n$,之后必然能成功，因此特别记 $f(i,j,n)$ 表示剩余容量不少于 $n$ 的概率，就可以将状态压缩到 $\mathcal O(n^3)$ 级别，很稳。

考虑转移：成功： $f(i,j+1,k+a_i)\leftarrow^+p_i\times f(i-1,j,k)$,失败：$f(i,j,k)\leftarrow ^+(1-p_i)\times f(i-1,j,k)$

复杂度$\mathcal O(n^3)$

注意实现时要平移数组，避免负数

#define MAXN 211
double f[MAXN][MAXN][MAXN<<1|1],p[MAXN];
int main()
{
    int n=read(),L=read(),k=read();
    if(k>n)k=n;
    double ans=0;
    f[0][0][n+k]=1;
    for(int i=1;i<=n;++i)scanf("%lf",&p[i]),p[i]/=100;
    for(int i=1;i<=n;++i)
    {
        int x=read();
        for(int j=0;j<i;++j)
            for(int k=0;k<=n+n;++k)
                if(k+x>=0)
                    f[i][j+1][min(n+n,k+x)]+=p[i]*f[i-1][j][k],f[i][j][k]+=(1-p[i])*f[i-1][j][k];
    }
    for(int j=L;j<=n;++j)
        for(int k=n;k<=(MAXN<<1);++k)ans+=f[n][j][k];
    printf("%.6lf",ans);
    return 0;
}