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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100007

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100007

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