Description：

$N$ 项挑战，如果 $a_i\ge0$ ，挑战成功后可以获得一个容量为 $a_i$ 的包；如果 $a_i=-1$ ，挑战成功后可以得到一个物品，必须至少要成功 $L$ 次。已知每项挑战成功的概率，求能把得到的物品装进包中的概率。

$1\le n \le 200$

Solution：

设 $f[i][j][k]$ 表示到了第 $i$ 场比赛，已经赢了 $j$ 场，还有 $k$ 的容量的概率，转移为 $f[i][j][k]\times(1-p_i)\to f[i+1][j][k]$ 和 $f[i][j][k]\times p_i\to f[i + 1][j + 1][k +a[i]]$ 。 $k$ 可能很大，但物品大小只有一，所以 $\ge n$ 的状态其实是一样的， $i$ 要滚动。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 210

double f[2][MAXN][MAXN << 1];

double p[MAXN];

int a[MAXN];

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    f[0][0][k + MAXN] = 1;

    for(int i = 1;i <= n;++i)scanf("%lf",&p[i]);

    for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

    int cur = 0;

    for(int i = 1;i <= n;++i)

    {

    	cur = cur ^ 1;

    	for(int l = 0;l <= n;++l)

            for(int s = -n;s <= n;++s)

            	f[cur][l][s + MAXN] = 0;

        for(int l = 0;l <= n;++l)

        {

            for(int s = -n;s <= n;++s)

            {

                if(s + a[i] >= n)f[cur][l + 1][n + MAXN] += f[cur ^ 1][l][s + MAXN] * p[i] / (double)100;

                else f[cur][l + 1][s + a[i] + MAXN] += f[cur ^ 1][l][s + MAXN] * p[i] / (double)100;

                f[cur][l][s + MAXN] += f[cur ^ 1][l][s + MAXN] * (100 - p[i]) / (double)100;

            }

        }

    }

	double ans = 0;

	for(int l = m;l <= n;++l)

	{

		for(int s = 0;s <= n;++s)

		{

			ans += f[cur][l][s + MAXN];

		}

	}

    printf("%.6lf\n",ans);

    return 0;

}