期望
概率与数学期望
在概率论中，我们把一个随机实验的某种可能的结果称为样本点，把所有可能的结果构成的集合称为样本空间，在一个给定的样本空间中，随机事件就样本空间的自己，即若干个样本点构成的集合，随机变量就是把样本点映射为实数的函数，随机变量分为离散型和连续性两种，我们主要讨论离散型随机变量，即取值有限或可数的随机变量
定义
设样本空间为\(\Omega\)，若对于\(\Omega\)中的每一个随机事件\(A\)，都存在实值函数\(P(A)\)满足：
1.\(P(A)\ge 0\)
2.\(P(\Omega)=1\)
3.对于若干个两两互斥事件\(A_1,A_2……\)有\(\sum P(A_i)=P(\cup A_i)\)
则称\(P(A)\)为随机事件\(A\)发生的概率，通俗的讲，概率是对随机事件发生的可能性的度量，是一个\(0\sim 1\)的实数
定义
若随机变量\(X\)的取值有\(x_1,x_2……\)一个随机事件可以表示为\(X=x_i\),其概率为\(P(X=x_i)=p_i\),则称\(E(X)=\sum p_ix_i\)为随机变量\(X\)的数学期望，通俗的讲，数学期望是随机变量取值与其概率的乘积之和
性质
数学期望是线性函数，满足
\[E(ax+by)=aE(x)+bE(y) \]该性质非常重要，这是我们能够运用动态规划算法求解数学期望的基本依据
来一到非常简单的题：
守卫者的挑战
打开了黑魔法师 \(Vani\) 的大门，队员们在迷宫般的路上漫无目的地搜寻着关押 \(applepi\) 的监狱的所在地。
突然，眼前一道亮光闪过，“我，\(Nizem\)，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”。
瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为 \(K\) 的包包。
擂台赛一共有 \(N\) 项挑战，各项挑战依次进行。
第 \(i\) 项挑战有一个属性 \(a_i\)，如果 \(a_i\ge 0\)，表示这次挑战成功后可以再获得一个容量为 \(a_i\) 的包包；如果 \(a_i=−1\)，则表示这次挑战成功后可以得到一个大小为 \(1\) 的地图残片。
地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把获得的所有的地图残片都带走（没有得到的不用考虑，只需要完成所有 \(N\) 项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。
并且他们至少要挑战成功 \(L\) 次才能离开擂台。
队员们一筹莫展之时，善良的守卫者 \(Nizem\) 帮忙预估出了每项挑战成功的概率，其中第 \(i\) 项挑战成功的概率为 \(p_i%\)。
现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。
分析：
这题很容易想到\(DP\)，我们来观察\(DP\)的状态应该如何设计，很明显的背包容量一维，地图残片数量一维，挑战成功了几次一维，第几次挑战一维
不过我们可以发现，地图残片数量和背包容量可以合并，因为最终都是要装在背包里的，于是我们将状态里的背包容量设为实际背包容量减去地图残片数量
所以我们得到了动态规划的状态:设\(f[i][j][k]\)表示前\(i\)场比赛，赢了\(j\)场，背包剩余容量为\(k\)时的概率
但是我们注意，我们最多可以得到\(n\)个地图残片，于是\(k\)的最大值为\(n\)，超过的不用考虑
于是有状态转移方程：
\[f[i][j][k]=f[i-1][j-1][k-a_i]\times p_i+f[i-1][j][k]\times (1-p_i)(a_i\ge 0) \]\[f[i][j][k]=f[i-1][j-1][k+1]\times p_i+f[i-1][j][k]\times(1-p_i)(a_i=-1) \]当然，这道题我们用当前状态更新以后状态会更加容易：
\[f[i+1][j+1][k+a_{i+1}]+=f[i][j][k]\times p_{i+1} \]\[f[i+1][j][k]+=f[i][j][k]\times (1-p_{i+1}) \]在统计答案的时候把所有\(i=n,j\ge L,k\ge 0\)的状态的概率加起来就行,需要注意的是，我们只需要最后\(k\ge 0\)，在\(DP\)中\(k\)可能会炸成负数，于是我们需要平移数组，复杂度\(O(n^3)\)
using namespace std;
int a[205],n,l,k;
double p[205],ans,f[205][205][415];
void init(){
scanf("%d%d%d",&n,&l,&k);
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)p[i]/=100;
f[0][0][k+n]=1;
}
void solve(){
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
for(int k=0;k<=n+n;k++){
if(a[i+1]+k>=0){
f[i+1][j+1][min(n+n,k+a[i+1])]+=f[i][j][k]*p[i+1];
f[i+1][j][k]+=f[i][j][k]*(1-p[i+1]);
}
}
}
}
for(int i=l;i<=n;i++){
for(int k=n;k<=n+n;k++){
ans+=f[n][i][k];
}
}
}