首页 > 代码库 > UVA 12723 Dudu, the Possum --数学期望

UVA 12723 Dudu, the Possum --数学期望

2024-07-13 16:30:32   218人阅读

题意不说了，概率和期望值要分开处理，可以先算出到达每层的概率，然后再乘以每层的期望，每层的期望是固定的。也可以从后往前直接推期望。

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define N 100007double ex[516];double dp[514];double pk[13];double C[504][25],X[504][24];double sum[13];int main(){    int t,cs = 1,i,j,k;    int n,m,K,Q;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&K);        for(i=1;i<=K;i++)            scanf("%lf",&pk[i]);        for(i=1;i<=n;i++)        {            scanf("%d",&Q);            ex[i] = 0.0;            for(j=1;j<=Q;j++)            {                scanf("%lf%lf",&C[i][j],&X[i][j]);                ex[i] += C[i][j]*X[i][j];            }        }        memset(dp,0,sizeof(dp));        dp[1] = 1;  //dp is probability        for(i=2;i<=n;i++)        {            for(k=1;k<=K;k++)            {                if(i-k >= 1)                    dp[i] += dp[i-k]*pk[k];            }        }        double res = 0;        for(i=1;i<=n;i++)            res += dp[i]*ex[i];        printf("Case #%d: %.6lf\n",cs++,res);    }    return 0;}
View Code
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define N 100007double ex[516];double dp[514];double pk[13];double C[504][25],X[504][24];double sum[13];int main(){    int t,cs = 1,i,j,k;    int n,m,K,Q;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&K);        for(i=1;i<=K;i++)            scanf("%lf",&pk[i]);        for(i=1;i<=n;i++)        {            scanf("%d",&Q);            ex[i] = 0.0;            for(j=1;j<=Q;j++)            {                scanf("%lf%lf",&C[i][j],&X[i][j]);                ex[i] += C[i][j]*X[i][j];            }            dp[i] = ex[i];        }        for(i=n;i>=1;i--)        {            for(k=1;k<=K;k++)            {                if(i+k <= n)                    dp[i] += dp[i+k]*pk[k];            }        }        printf("Case #%d: %.6lf\n",cs++,dp[1]);    }    return 0;}
View Code


联系
我们