题解：UVA12723 Dudu, the Possum

· · 题解

::::info[简化题意]{open}

有一个有 n 层的架子，初始时在第一层（最高层设为第 1 层，最低层设为第 n 层）。

第 i 层上有 q_i 个食物，对于第 i 层第 j 份食物，它可以提供 c_{i,j} 的卡路里，并且有 x_{i,j} 的概率选到它。

最多一次向下 k 层，往下 i 层的概率为 p_i。

每当到达某一层时，选择一份食物吃掉，得到它提供的卡路里，然后前往下一层。

如果当前层数大于 n 则称为离开了架子。

输出在离开架子前，预期会吸收多少卡路里？

::::

::::info[思路]

我们定义 dp 数组，dp_i 表示到达第 i 层的概率。

因为我们初始在第 1 层，所以初始化时 dp_1 等于 1。

期望总卡路里等于每一层 i 的 dp_i 乘以该层的期望卡路里之和。

::::

::::success[Code]

#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;
}

/*
｀　　　　　　　　　　　　　　　　　　　　　　　４　　　　０００　　　　　　４
　　　　　　　　　　　　　　　　　　　　　　　４４　　　０　　　０　　　　４４
ｘ　　　ｘ　　ｙ　　　ｙ　　ｘ　　　ｘ　　　　４４　　　０　　　０　　　　４４
ｘ　　　ｘ　　ｙ　　　ｙ　　ｘ　　　ｘ　　　４　４　　　０　　　０　　　４　４
　ｘ　ｘ　　　ｙ　　　ｙ　　　ｘ　ｘ　　　　４　４　　　０　　　０　　　４　４
　　ｘ　　　　　ｙ　ｙ　　　　　ｘ　　　　４　　４　　　０　　　０　　４　　４
　ｘ　ｘ　　　　ｙ　ｙ　　　　ｘ　ｘ　　　４４４４４　　０　　　０　　４４４４４
ｘ　　　ｘ　　　　ｙ　　　　ｘ　　　ｘ　　　　　４　　　０　　　０　　　　　４
ｘ　　　ｘ　　　　ｙ　　　　ｘ　　　ｘ　　　　　４　　　　０００　　　　　　４
　　　　　　　ｙｙ
*/

::::

::::info[AI 使用说明]

使用了通义千问进行翻译，并由人工进行简化。

::::