题意不说了，概率和期望值要分开处理。
方法1：可以先算出到达每层的概率，然后再乘以每层的期望，每层的期望是固定的。
方法二：也可以从后往前直接推期望。为什么从后往前呢？因为第i层的时候，它可以跳到的层是不确定的，所以还不能知道那一层的期望，所以不能计算。
设dp[i]为从第i层跳到最底层能得到的值的期望，那么从后往前推就有dp[i] = dp[i+k]*p[k]; 此时dp[i+k]已知，最后dp[1]就是答案。
注意一点就是：顺着走是求的概率，而从后推到前才是期望。
#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 ",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 ",cs++,dp[1]); } return 0; }