概率DP light oj 1030

t组数据

n块黄金

到这里就捡起来出发点1 到n结束点+位置>n 重掷一次

dp[i] 代表到这里的概率

dp[i]=(dp[i-1]+dp[i-2]... )/6 如果满6个的话

否则处理一下

然后期望就是 sum+=dp[i]*z[i];

 1 #include <stdio.h>
 2 #include<algorithm>
 3 #include<math.h>
 4 #include<string.h>
 5 
 6 using namespace std;
 7 
 8 #define MAXN 100010
 9 
10 double dp[MAXN];
11 int    z[MAXN];
12 
13 int main()
14 {
15     int t,ca;
16     scanf("%d",&t);
17     ca=1;
18 
19     while (t--)
20     {
21         int n;
22         scanf("%d",&n);
23 
24         for(int i=1;i<=n;i++)
25             scanf("%d",&z[i]);
26         memset(dp,0,sizeof(dp));
27 
28         dp[1]=1;
29 
30         for(int i=1;i<n;i++)
31         {
32             int x=min(n-i,6);
33 
34             for(int j=1;j<=x;j++)
35                 dp[i+j]+=dp[i]/x;
36         }
37         double sum=0;
38         for(int i=1;i<=n;i++)
39         {
40             sum=sum+dp[i]*z[i];
41         }
42         printf("Case %d: %.6lf
",ca++,sum);
43     }
44 
45     return 0;
46 }