题解：UVA12723 Dudu, the Possum

xyx4042025-10-012025-10-08

引用站外地址，不保证站点的可用性和安全性

洛谷文章链接

xyx404

简化题意

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

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

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

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

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

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

思路

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

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

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

代码

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





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