{% link 洛谷文章链接,xyx404,https://www.luogu.com.cn/article/k61kz6f9 %}
{% folding blue open, 简化题意 %}
有一个有 $n$ 层的架子，初始时在第一层（最高层设为第 $1$ 层，最低层设为第 $n$ 层）。
第 $i$ 层上有 $q_i$ 个食物，对于第 $i$ 层第 $j$ 份食物，它可以提供 $c_{i,j}$ 的卡路里，并且有 $x_{i,j}$ 的概率选到它。
最多一次向下 $k$ 层，往下 $i$ 层的概率为 $p_i$。
每当到达某一层时，选择一份食物吃掉，得到它提供的卡路里，然后前往下一层。
如果当前层数大于 $n$ 则称为离开了架子。
输出在离开架子前，预期会吸收多少卡路里？
{% endfolding %}
{% folding blue, 思路 %}
我们定义 $dp$ 数组，$dp_i$ 表示到达第 $i$ 层的概率。
因为我们初始在第 $1$ 层，所以初始化时 $dp_1$ 等于 $1$。
期望总卡路里等于每一层 $i$ 的 $dp_i$ 乘以该层的期望卡路里之和。
{% endfolding %}
{% folding green, 代码 %}
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int T;
int n,k;
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
cin>>T;
for(int i=1;i<=T;i++){
cin>>n>>k;
vector<double>p(k+1),dp(n+1,0);
dp[1]=1;
for(int i=1;i<=k;i++)cin>>p[i];
double ans=0;
for(int i=1;i<=n;i++){
int l;cin>>l;
double sum=0;
for(int j=1;j<=l;j++){
double c,x;cin>>c>>x;
sum+=c*x;
}
for(int j=1;j<=k&&i-j>0;j++){
dp[i]+=dp[i-j]*p[j];
}
ans+=dp[i]*sum;
}
printf("Case #%d: %.6lf\n",i,ans);
}
return 0;
}
/*
｀ ４ ０００ ４
４４ ０ ０ ４４
ｘ ｘ ｙ ｙ ｘ ｘ ４４ ０ ０ ４４
ｘ ｘ ｙ ｙ ｘ ｘ ４ ４ ０ ０ ４ ４
ｘ ｘ ｙ ｙ ｘ ｘ ４ ４ ０ ０ ４ ４
ｘ ｙ ｙ ｘ ４ ４ ０ ０ ４ ４
ｘ ｘ ｙ ｙ ｘ ｘ ４４４４４ ０ ０ ４４４４４
ｘ ｘ ｙ ｘ ｘ ４ ０ ０ ４
ｘ ｘ ｙ ｘ ｘ ４ ０００ ４
ｙｙ
*/
{% endfolding %}